백준 1504번 특정한 최단 경로 풀러 가기

문제 설명

입력

• 첫 줄에는 정점의 수와 간선의 수가 주어진다.
• 그 다음 줄부터 간선 정보가 주어진다. ( a b c = a에서 b까지 가는 거리는 c )
• 마지막 줄에 반드시 거쳐야 하는 두 정점이 주어진다.

구해야 하는 것 및 특이점

마지막 줄에 주어진 두 노드를 지나면서 + 1번 노드에서 마지막 노드(4번 노드)까지 가는 최단 거리는?

• 이동했던 간선 다시 이동 가능 ( → 하지만 다시 이동하면 최단 거리가 아니게 되므로 무시해도 되는 조건 )
• 거리는 항상 양수
• 최단 경로가 없다면 -1을 출력

예제 설명

1번 노드에서 4번 노드로 가는 최단 거리를 구하면 4이다.
하지만, 우리는 2번 노드와 3번 노드를 반드시 지나야 하므로, 최단 경로는 파란색으로 표시한 길이 되고, 이 때 답은 7이다.

구현 아이디어

반드시 지나야 하는 두 노드를 A, B라고 하자.
A, B를 지나는 최단거리는

• 1번 노드 → A → B → 4번 노드
• 1번 노드 → B → A → 4번 노드

두 가지 방법이 있다. 그러므로 두 가지 최단 경로를 구하고, 둘 중 작은 것을 선택하자!

이 때 최단 거리는 1번 노드 → 4번 노드로 보지 말고
🍒1번 노드 → A / A → B / B → 4번 노드 로 나눠서 보자🍒

모든 노드에 대한 최단 거리는 필요하지 않고 음수 간선이 없기 때문에, 최단 거리 알고리즘으로 우선순위 큐를 활용한 다익스트라 알고리즘을 사용하여 구현하였다.

우선순위 큐를 활용한 다익스트라 알고리즘은 최단 경로 알고리즘 글을 참고하자!

1트 - 시간 초과

import sys
import heapq

input = sys.stdin.readline

INF = 1e6 # 무한을 나타내는 변수

n, e = map(int, input().split()) # 정점, 간선의 개수

graph = [[] for _ in range(n+1)] # 그래프 정보를 담을 리스트

# 입력
for _ in range(e):
    # a에서 b로 가는 거리가 c
    a, b, c = map(int, input().split())
    # 무방향 그래프이므로 양쪽에 모두 원소 추가
    graph[a].append((b, c))
    graph[b].append((a, c))
    
# 반드시 지나야 할 두 노드
v1, v2 = map(int, input().split())

def dijkstra(start):
	# 현재까지의 최단 경로를 담을 리스트
    d = [INF for _ in range(n+1)]
    d[start] = 0
	
    # 우선순위 큐
    q = []
    heapq.heappush(q, (start, 0))

    while q:
        now, dist = heapq.heappop(q)
        # 인접 노드를 탐색
        for node, w in graph[now]:
            # 현재 최단거리가 현재 노드를 거쳐가는 것보다 작으면 pass
            if d[node] < d[now] + w:
                continue
            # 최단거리 갱신
            d[node] = d[now] + w
            heapq.heappush(q, (node, w))

    return d

one = dijkstra(1) # 1번 노드에서 다른 노드로 가는 최단 경로
v1_arr = dijkstra(v1) # v1 노드에서 다른 노드로 가는 최단 경로
v2_arr = dijkstra(v2) # v2 노드에서 다른 노드로 가는 최단 경로

# 둘 중 더 작은 값을 출력
first = one[v1] + v1_arr[v2] + v2_arr[n]
second = one[v2] + v2_arr[v1] + v1_arr[n]

result = min(first, second)

if result == INF:
    result = -1

print(result)

2트 - 틀렸습니다

위 코드의 문제점

1️⃣ 우선순위 큐에 삽입한 튜플의 순서가 틀렸다.

• 튜플의 첫 번째 원소를 기준으로 정렬되기 때문에 거리를 튜플의 첫 번째 원소로 두어야 한다.

2️⃣ for 문 안에서 최단 거리인지 아닌지 검사함 → if d[node] < d[now] + w

• dist를 간선 정보가 아니라 누적 거리로 하면 for 문 밖에서 최단 거리인지 검사가 가능해지므로 연산 횟수를 줄일 수 있다.

def dijkstra(start):
    d = [INF for _ in range(n+1)]
    d[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)
        if d[now] < dist:
            continue
        for node, w in graph[now]:
            cost = dist + w
            if cost < d[node]:
                d[node] = cost
                heapq.heappush(q, (cost, node))

    return d

3트 - 맞았습니다

위 코드의 문제점

• result == INF일 때 -1을 출력하도록 했는데, one[v1], v1_arr[v2], v2_arr[n] 셋 중 하나가 INF가 나오면 result는 INF보다 커진다.

그러므로 result == INF에서 ==를 <로 수정해야 한다.

print(result if result < INF else -1)