[BOJ/python]9370번 미확인 도착지점 + 오답 이유

백준 9370번 미확인 도착지점 파이썬

문제 링크 - https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

생각지도 못한 곳에서 계속해서 오답이 발생했다. 아마 나처럼 오답을 받고 검색하는 사람들이 꽤 될 것 같은 문제다.

---

최단 거리를 이동하면서 h→g 경로를 선택하는 경우가 무엇을 의미하는 지 파악하는 것이 중요하다.

s→g 까지의 최단거리가 s→h→g 인 경우에 h→g 경로를 선택하게 된다. 반대로 s→h 까지의 최단거리가 s→g→h 인 경우에는 g→h 경로를 선택하게 된다.

두 경우를 고려하지 않고 풀 수도 있지만 하나의 테스트 케이스에서 h→g 경로와 g→h 경로 모두 사용할 수 없다는 것도 중요한 사실이다. h→g / g→h 순서를 고려하고 푸는 방법과 경우를 나누지 않고 푸는 방법 모두 가능하다.

---

이제 목적지 후보 중 어떤 곳에 이동이 가능한 지 파악해야 한다.

t를 목적지 후보 중 하나라고 하자. s→ t 의 최단 거리가 s→h→g→t 인 경우에, h→g 경로를 선택하여 t로 이동할 것이다.

즉, s→t의 최단 거리가 s→h→g→t 혹은 s→g→h→t 인 경우에 h-g 경로를 선택하여 목적지 t로 이동한다.

1. 풀이

• s,g,h에서 시작하는 다익스트라를 통해 각 노드까지의 거리를 구한다.
• s→g 까지의 최단거리 + g-h 거리 + h→t 까지의 최단거리가 s→t 까지의 최단거리와 같다면 목적지 후보t 에 도착할 수 있다.
• 마찬가지로, s→h 까지의 최단거리 + h-g 거리 + g→t 까지의 최단거리가 s→t 최단거리와 같다면 목적지 후보 t에 도착할 수 있다.
• 두 경우 중 하나만 만족하면 answer 배열에 추가한다.

🚨주의 사항

만약 INF=float(’inf’)로 초기화하는 경우 오답이 발생할 수 있다. 만약 s→t 로 이동이 불가능하고 (거리 = INF), h→t 혹은 g→t의 이동도 불가능한 경우 목적지에 도착할 수 없지만, INF + INF = INF 가 되어 정답 처리를 하게 된다는 점을 고려해야 한다.

2.1 3번의 다익스트라 사용 코드

from heapq import heappop, heappush

def deijkstra(start):
    dist = [INF for _ in range(N+1)]
    dist[start]=0
    heap =[]
    heappush(heap, [0,start])
    while heap:
        weight,node = heappop(heap)
        
        if dist[node] < weight:
            continue
        
        for next, cost in G[node]:
            if dist[next]>weight+cost:
                dist[next] = weight + cost
                heappush(heap,[dist[next],next])
    
    return dist
    
INF = int(1e9)
T= int(input())
for _ in range(T):
    N,M,K = map(int, input().split())
    s,g,h = map(int, input().split())
    
    G=[[]for _ in range(N+1)]
    
    for _ in range(M):
        u,v,w = map(int, input().split())
        if (u==g and v==h) or (u==h and v==g):
            gToh = w
        G[u].append([v,w])
        G[v].append([u,w])
        
    candidate = {}
    for _ in range(K):
        candidate[int(input())]=1

    distFromS = deijkstra(s)
    distFromG = deijkstra(g)
    distFromH = deijkstra(h)

    answer = []
    for i in candidate:
        if ( distFromS[g] + gToh + distFromH[i] == distFromS[i] ) or ( distFromS[h] + gToh+ distFromG[i] == distFromS[i] ):
            answer.append(i)
                
    answer.sort()
    print(*answer)

2.2 2번의 다익스트라 사용 코드

만약 s→h→g 경로를 선택한다면, dist[g] = g-h거리 + dist[h] 일 것이고 s→g→h 경로를 선택한다면, dist[h]= g-h거리 + dist[g] 인 점을 이용하여 두 번의 다익스트라만 계산하여 풀 수 있다.

만약 h→g 경로를 이용한다면, s→g 최단거리 + g→t 최단거리 = s→t 최단거리인 경우에 목적지 후보에 도착할 수 있다.

from heapq import heappop, heappush

def deijkstra(start):
    dist = [INF for _ in range(N+1)]
    dist[start]=0
    heap =[]
    heappush(heap, [0,start])
    while heap:
        weight,node = heappop(heap)
        
        if dist[node] < weight:
            continue
        
        for next, cost in G[node]:
            if dist[next]>weight+cost:
                dist[next] = weight + cost
                heappush(heap,[dist[next],next])
    
    return dist
    
INF = int(1e9)
T= int(input())
for _ in range(T):
    # global N,G
    N,M,K = map(int, input().split())
    s,g,h = map(int, input().split())
    
    G=[[]for _ in range(N+1)]
    
    for _ in range(M):
        u,v,w = map(int, input().split())
        G[u].append([v,w])
        G[v].append([u,w])
        
    candidate = {}
    for _ in range(K):
        candidate[int(input())]=1

    distFromS = deijkstra(s)
    if distFromS[g] > distFromS[h]:
        newStart = g
    elif distFromS[g] < distFromS[h]:
        newStart = h
        
    distFromNewS = deijkstra(newStart)
    answer = []
    for i in candidate:
        if distFromS[newStart] + distFromNewS[i] == distFromS[i]:
            answer.append(i)
    answer.sort()
    print(*answer)