특정한 최단 경로
| 1 초 | 256 MB | 117327 | 33913 | 23219 | 26.770% |
문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
예제 입력 1
4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3
예제 출력 1
7
출처
- 문제의 오타를 찾은 사람: ZZangZZang
- 데이터를 추가한 사람: alex9801, paldad, rhdqor213
3개월 전에 대충 다익스트라 템플릿만 외워서 찍어내기 식으로 공부했었는데, 그 덕분에 이제 코테에서 다익스트라가 등장해도 "음, 다익스트라군" 하고 인지만 가능하고 구현은 할 수 없는 (까먹은) 깡통 개가 되어버렸다.
내가 개발자라고 해도 될까? 라는 의문에서 그냥 개.가 되었다.
그래서 간단하게 BOJ 1504에 대해 리뷰하려고 한다.
우선 전체 코드는 다음과 같다.
import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize
def dijkstra(start, graph, nodes):
dist = [INF] * (nodes + 1)
dist[start] = 0
heap = [(0, start)]
# heapq.heappush(heap, (0, start))
while heap:
# current_dist는 힙에서 꺼낸 기록상 거리.
# now는 현재 노드 번호
current_dist, now = heapq.heappop(heap)
# 최단경로니까 이런 경우 업데이트 할 필요가 없음
# heap = [(6, 5), (10, 5)]
# dist[5] = 6
if dist[now] < current_dist:
continue
for next_node, cost in graph[now]:
new_cost = current_dist + cost
if new_cost < dist[next_node]:
dist[next_node] = new_cost
heapq.heappush(heap, (new_cost, next_node))
return dist
if __name__ == "__main__":
nodes, edges = map(int, input().split())
graph = [[] for i in range(nodes+1)]
for _ in range(edges):
a, b, c = map(int, input().split())
graph[a].append((b,c))
graph[b].append((a,c))
v1, v2 = map(int, input().split())
dist1 = dijkstra(1, graph, nodes) # dist1[x] 1에서 x까지 최단거리
dist_v1 = dijkstra(v1, graph, nodes) # dist_v1[x] v1에서 x까지 최단거리
dist_v2 = dijkstra(v2, graph, nodes) # dist_v2[x] v2에서 x까지 최단거리
path1 = dist1[v1] + dist_v1[v2] + dist_v2[nodes]
path2 = dist1[v2] + dist_v2[v1] + dist_v1[nodes]
answer = min(path1, path2)
print(-1 if answer >= INF else answer)
문제의 핵심 조건
시작: 1번 노드
도착: N번 노드
반드시 지나야 하는 노드: v1, v2
즉, 가능한 경로는 반드시 아래 조건을 만족해야 한다.
1 → ... → v1 → ... → v2 → ... → N
또는
1 → ... → v2 → ... → v1 → ... → N
입출력
우선 입력을 받아야 하므로, 다음과 같이 착실히 받아준다.
이때 양방향 그래프임을 유의하자. 따라서 빈 graph를 만들어주고 양방향으로 입력받아 추가해준다.
if __name__ == "__main__":
node, edge = map(int, input().split())
graph = [[] for _ in range(node + 1)]
for _ in range(edge):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
v1, v2 = map(int, input().split())
문제 조항을 보면, v1과 v2를 입력받고 해당 노드를 '반드시' 지나가야 하는 최단경로를 만들어야 한다.
따라서 시작 위치인 1에서 v1까지 가는 최단 경로, v1에서 v2까지 가는 최단 경로를 각각 구해서 더해주면 된다. 더불어 1에서 v2로 가는 최단경로와 v2에서 v1으로 가는 최단 경로를 구해서 더하는 것도 동일 방식으로 작동하게끔 하여 최소값을 구하면 문제 요구를 충족할 수 있다.
이는 곧 3번의 다익스트라를 돌리는 것과 동일하다.
따라서 모든 출발점에서 모든 노드까지 다익스트라를 3번 돌려준다.
dist[x] 라고 하면, 시작 위치에서부터 x까지의 최단거리를 계산한 것이다.
dist1 = dijkstra(1, graph, node)
dist_v1 = dijkstra(v1, graph, node)
dist_v2 = dijkstra(v2, graph, node)
이렇게 구한 거리를 가지고, 가능한 모든 경로를 구해준다.
path1은 1에서부터 v1까지의 최단거리 + v1에서 v2까지의 최단거리 + v2에서 N까지 최단거리를 구한 값이다.
반대로 path2은 1에서부터 v2까지의 최단거리 + v2에서 v1까지의 최단거리 + v1에서 N까지 최단거리를 구한 값이다.
path1 = dist1[v1] + dist_v1[v2] + dist_v2[node]
path2 = dist1[v2] + dist_v2[v1] + dist_v1[node]
다익스트라는 한 번 실행하면 한 출발점에서 모든 노드까지 최단거리를 구한다. 따라서 경로 전체를 직접 찾는 것이 아니라 필요한 구간들을 따로 계산해서 더하는 방식을 사용한다. 이는 다익스트라가 최단경로의 부분 경로도 최단이라는 성질을 가지고 있기 때문이다.
따라서 쪼개서 계산이 가능하다.
이렇게 구한 path 중 더 작은 값을 프린트 하면 입출력은 완료이다.
answer = min(path1, path2)
print(-1 if answer >= INF else answer)
다익스트라 알고리즘
def dijkstra(start, graph, nodes):
dist = [INF] * (nodes + 1)
dist[start] = 0
heap = [(0, start)]
while heap:
current_dist, now = heapq.heappop(heap)
if dist[now] < current_dist:
continue
for next_node, cost in graph[now]:
new_cost = current_dist + cost
if new_cost < dist[next_node]:
dist[next_node] = new_cost
heapq.heappush(heap, (new_cost, next_node))
return dist
다익스트라 알고리즘을 위해 heapq와 INF 값을 준비해야 한다.
INF값은 큰 수를 통해 최단경로를 명확하게 가름하기 위함으로, 정해진 수는 존재하지 않는다.
나는 import sys 를 통해 sys.maxsize로 설정하였다.
import heapq
INF = int(1e9) # 이렇게 해도 됨
입력값 의미
함수 dijkstra의 인자로 시작 노드인 start, 그래프 정보인 graph, 전체 노드의 개수인 node가 들어간다.
graph는 다음과 같이 구성되어 있으며
graph = [
[],
[(2, 2), (3, 5)],
[(3, 1), (4, 2)],
[(4, 3)],
[]
]
이는 다음과 같다.
1번 노드 → 2번 노드, 비용 2
1번 노드 → 3번 노드, 비용 5
2번 노드 → 3번 노드, 비용 1
2번 노드 → 4번 노드, 비용 2
3번 노드 → 4번 노드, 비용 3
즉, graph[now] 는 now 노드에서 갈 수 있는 다음 노드들의 목록이다.
dist 배열
dist = [INF] * (node + 1)
dist[i]는 start에서 i번 노드까지 현재까지 알고 있는 최단거리를 의미한다.
처음에는 아무 노드까지의 거리를 모르므로 전부 큰 값인 INF로 채운다.
dist = [INF, INF, ..., INF]
이때, 시작할 노드인 start에 대해서는 0으로 설정한다.
dist[start] = 0
heap의 의미
heap = [(0, start)]
힙에는 (거리, 노드) 정보가 들어간다. 예를 들어 (0, 1)은 1번 노드까지 거리 0으로 갈 수 있다는 뜻이다.
다익스트라는 항상 현재 갈 수 있는 노드 중 가장 거리가 짧은 노드부터 확인하므로, 일반 큐가 아닌 heapq를 사용한다.
가장 작은 값을 먼저 꺼내주기 때문이다.
while문을 사용해 힙에 확인할 후보가 남아있는 동안 계속 반복한다.
처음에는 이렇게 시작한다.
heap = [(0, 1)]
이제 힙에서 가장 거리가 짧은 후보를 꺼낸다.
current_dist, now = heapq.heappop(heap)
이제 current_dist가 0, now가 1이다. dist[now]가 현재까지 알고있는 now까지 최단거리가 된다.
힙에는 같은 노드가 여러 번 들어갈 수 있다.
예를 들어 5번 노드까지 가는 방법이 처음에는 비용 10으로 발견되면 아래와 같다.
heap = [(10, 5)]
dist[5] = 10
그런데 나중에 더 좋은 경로가 발견될 수 있다.
dist[5] = 6
heap = [(6, 5), (10, 5)]
이제 heap에는 5번 노드에 대한 기록이 두 개 있으나, 이미 dist[5]는 6이므로 (최단경로이므로) (10, 5)는 더 이상 볼 필요가 없다.
그러므로 아래와 같이 조건을 두어 최단 경로에 대해서만 heap이 수행하게끔 한다.
if dist[now] < current_dist:
continue
현재 노드에서 갈 수 있는 노드 확인
이제 현재 노드인 now에서 갈 수 있는 노드들을 하나씩 살펴보고, 최단 경로를 찾자.
for next_node, cost in graph[now]:
예를 들어
graph[1] = [(2, 2), (3, 5)]
이면, 첫번째 반복에서는
next_node = 2
cost = 2
두번째 반복에서는
next_node = 3
cost = 5
이다.
이는 1번에서 2번으로 가는 비용은 2, 1번에서 3번으로 가는 비용은 5라는 뜻이다.
이제 현재 노드까지 온 비용에 다음 노드로 가는 비용을 더한다.
new_cost = current_dist + cost
예를 들어 현재 1번 노드에 있고, current_dist = 0 이면 new_cost = 2가 된다.
최단 경로 갱신
기존에 알고 있던 거리보다 새로 계산한 거리가 더 짧으면 갱신한다.
if new_cost < dist[next_node]:
dist[next_node] = new_cost
heapq.heappush(heap, (new_cost, next_node))
예를 들어
dist[2] = INF
new_cost = 2
이면 2 < INF 이므로 갱신한다.
dist[2] = 2
heapq.heappush(heap, (2, 2))
이는 2번 노드까지 최단거리가 2로 갱신되었으며, 나중에 2번 노드도 확인해야 하므로 heap에 넣는다는 뜻이다.
핵심 요약
1. 시작 노드의 거리를 0으로 둔다.
2. 힙에 시작 노드를 넣는다.
3. 힙에서 가장 거리가 짧은 노드를 꺼낸다.
4. 그 노드에서 갈 수 있는 다음 노드들을 본다.
5. 더 짧은 경로를 발견하면 dist를 갱신한다.
6. 갱신된 노드를 다시 힙에 넣는다.
7. 힙이 빌 때까지 반복한다.
최단 경로를 구하는 방식
최단 경로를 구하는 방식은 다익스트라, 벨만 포드, 플로이드워셜 등이 존재한다.
그런데 어떨 때 다익스트라(Dijkstra)를 쓰는가를 생각해보면, 한 출발점에서 모든 노드까지의 최단거리를 구할 때이다.
현재까지 가장 가까운 노드로부터 확정해 나가는 그리디 방식이다.
벨만-포드(Bellman-Ford)는 다익스트라와 달리 음수 간선이 허용되며 음수 사이클을 탐지할 수 있다.
모든 간선을 V-1번 반복해서 거리를 갱신하므로 시간복잡도가 느리다.
플로이드-워셜(Floyd-Warshall)은 모든 노드에서 모든 노드의 최단거리를 구하는 all-pairs shortest path이다. (DP)
중간 노드를 하나씩 허용하면서 거리를 갱신하므로 시간복잡도가 매우 느리다.
음수 간선은 가능하나, 음수 사이클이 있다면 의미가 없다.
---------------
사담으로 오늘이 BOJ 섭종 날이다.
아직 백준을 씹고 뜯고 맛보지 못한 초보 개로서 너무 아쉽다.
누군가의 백준 형식지를 보고 그저 챗 선생과 함께 할 수 밖에..
'CODE > Algorithm (Python)' 카테고리의 다른 글
| BOJ 1544 사이클 단어 (0) | 2026.04.28 |
|---|---|
| BOJ 4485 녹색 옷 입은 애가 젤다지? (0) | 2026.04.28 |
| 프로그래머스 level 1 명예의 전당(1) (0) | 2026.04.27 |
| 프로그래머스 level 1 비밀지도 (0) | 2026.04.27 |
| 프로그래머스 level 1 문자열 나누기 (0) | 2026.04.27 |