[백준] 1504 특정한 최단 경로 - 골드4

 

 

오늘의 문제

 

https://www.acmicpc.net/problem/1504

---

오늘의 학습 키워드

• 다익스트라 알고리즘

 

---

1. 문제설명

 

 

방향성이 없는 그래프가 주어집니다.

1번 정점에서 N번 정점으로 이동하는 최단 거리를 구하려고 하는데 반드시 거쳐야 하는 두 경로가 존재합니다.

 

해당 두 경로를 거쳐 N번 정점으로 도착가능한 경우 해당 경로의 최단거리를 출력하는 문제입니다.

---

제한사항

• 시간 제한 1초
• 메모리 제한 256MB
• 2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000
• 1 ≤ c ≤ 1,000
• v1 ≠ v2, v1 ≠ N, v2 ≠ 1

---

2. 접근방식

우선 말을 이해할 수 있게 바꿔 보겠습니다.

 

시작 정점은 항상 1번이고 1번에서 출발해 N번 정점으로 이동하려고 하는데 반드시 거쳐야 하는 두 정점 v1, v2가 주어집니다.

 

즉 이동 경로는 반드시 1 -> v1 -> v2 -> N 혹은 1 -> v2 -> v1 -> N 으로 이동해야 합니다.

 

왜냐하면 방향성이 없는 그래프 이기 때문입니다.

 

그러면 다익스트라 알고리즘을 활용하여 노드와 간선을 입력받고 가중치를 입력하여 최단 경로를 구해 보겠습니다.

 

이번 문제에서 생각할 부분은 이동 경로입니다.

 

---

 

3. 코드

import sys, heapq
input = sys.stdin.readline

# 시작위치에서 도착 위치를 기준으로 최단경로 구하는 다익스트라
def dijkstra(start, end):
    distance = [1e9] * (N + 1)
    distance[start] = 0
    heap = [[0, start]]

    while heap:
        cost, node = heapq.heappop(heap)
        for next_cost, next_node in graph[node]:
            if cost + next_cost < distance[next_node]:
                distance[next_node] = cost + next_cost
                heapq.heappush(heap, [cost + next_cost, next_node])
    
    return distance[end]

# 입력
N, E = map(int, input().split())

# 간선의 정보를 담은 그래프
graph = [[] for _ in range(N+1)]
distance = [1e9] * (N + 1)          # 거리별 가중치 

# 간선 정보 업데이트
for _ in range(E):
    a_node, b_node, weight = map(int, input().split())
    graph[a_node].append((weight, b_node))
    graph[b_node].append((weight, a_node))

# 반드시 거쳐야 하는 노드
v1, v2 = map(int, input().split())

path1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
path2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)

if path1 >= 1e9 and path2 >= 1e9:
    print(-1)
else:
    print(min(path1, path2))

 

---

코드설명

1. 우선 입력을 받고 그래프를 업데이트 해주겠습니다.

# 입력
N, E = map(int, input().split())

# 간선의 정보를 담은 그래프
graph = [[] for _ in range(N+1)]
distance = [1e9] * (N + 1)          # 거리별 가중치 

# 간선 정보 업데이트
for _ in range(E):
    a_node, b_node, weight = map(int, input().split())
    graph[a_node].append((weight, b_node))
    graph[b_node].append((weight, a_node))

 

 

정점의 갯수 N, 간선의 갯수 E를 입력받고 E번 반복하며 간선의 정보를 업데이트 해줍니다.

방향이 없는 양방향 그래프이므로 a 노드에서 b노드로 가는 가중치를 그래프 a위치에 업데이트 해주고

b노드에서 a노드로 가는 가중치역시 b노드에 업데이트 해줍니다.

 

2. 다익스트라 알고리즘을 작성해 줍니다.

# 시작위치에서 도착 위치를 기준으로 최단경로 구하는 다익스트라
def dijkstra(start, end):
    distance = [1e9] * (N + 1)
    distance[start] = 0
    heap = [[0, start]]

    while heap:
        cost, node = heapq.heappop(heap)
        for next_cost, next_node in graph[node]:
            if cost + next_cost < distance[next_node]:
                distance[next_node] = cost + next_cost
                heapq.heappush(heap, [cost + next_cost, next_node])
    
    return distance[end]

 

시작 위치를 기준으로 종료 위치까지 이동하는 최단 거리를 구하는 다익스트라 알고리즘 입니다.

 

입력받은 start값을 기준으로 heap을 사용해 최소값을 구해줍니다.

 

시작위치와 자기자신에 대한 가중치를 0으로 입력해 준 heap을 만들고 while문을 통해 최소 가중치를 구해주는 코드입니다.

 

heap에는 시작 위치 예를들어 1번이 들어온 경우 1번과 연결된 노드정보는 graph[1]에 [가중치와 다음노드] 순서로 저장되어 있습니다.

 

여기서 현재 가중치는 0이고 다음 노드로 가는 가중치는 다음노드에 적힌 가중치 입니다.

 

따라서 for 문을 이용해 현재 노드에서 다음 노드로 가는 모든 정보를 꺼내어 가중치를 확인하고 그 값을 distance 배열에 업데이트 해줍니다.

 

그렇게 해서 모든 노드를 탐색했을 때 시작위치에서 종료 위치까지 가는데 걸린 가중치는 distance[end]에 저장되어 있으니 해당 가중치를 반환해 줍니다.

 

3. 반드시 거쳐야 하는 노드 v1 과 v2가 존재하니 경로는 1 -> v1 -> v2 -> N 과 1 -> v2 -> v1 -> N 두 경로가 존재합니다.

# 반드시 거쳐야 하는 노드
v1, v2 = map(int, input().split())

path1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
path2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)

if path1 >= 1e9 and path2 >= 1e9:
    print(-1)
else:
    print(min(path1, path2))

 

따라서 반드시 거쳐야 하는 경로 v1, v2를 입력받고 해당 경로를 포함하는 경로 path1 과 path2를 작성해 줍니다.

 

path1은 1번 정점에서 v1으로 가는 가중치 + v1에서 v2로 가는 가중치 + v2에서 N까지 가는 가중치를 더한 값이고

path2는 1번 정점에서 v2로 가는 가중치 + v2에서 v1 으로 가는 가중치 + v1에서 N까지 가는 가중치를 더한 값입니다.

 

이제 해당 노드를 방문하여 N까지 가는데 경로가 연결되어 있다면 최대값으로 초기화한 distance보다 무조건 값이 작을것 입니다.

 

만약 갈 수 없다면 path1과 path2 모두 값이 1e9 이상 나올 것입니다.

---

 

4. 결과

---

 

회고

간만에 푼 다익스트라 문제입니다.

처음 조건을 보고 단순히 다익스트라 한번 돌려서 시작에서 도착까지 가는 최소경로는 구했는데 특정 경로는 어떻게 방문하지 에서 막혔었습니다.

 

해결법을 찾으려고 고민하다가 도저히 머리속에서 떠오르지 않아 알고고수 형에게 물어봤고 시작위치에서 도착정점까지 가려면 v1과 v2를 반드시 거치는 경로 2개가 나온다는 설명을 듣고 풀 수 있었습니다.

 

기존에 다익스트라 문제는 많이 풀었던 문제였어서 생각보다 쉽게 개념이 떠올랐고 구글링을 통해 heap을 사용하는 다익스트라 알고리즘 코드를 한번 보고 나니 확실히 개념이 잡혀 조금 시간이 걸렸지만 해결할 수 있었던 문제 였습니다.

 

내일은 구현과 관련된 문제를 해결해 보겠습니다.