미확인 도착지

 

9370번: 미확인 도착지

백준 온라인 저지 9370번 미확인 도착지 문제입니다.

어떤 사람이 목적지까지 최단 경로로 간다는 가정으로 문제가 시작합니다. 이 사람이 출발한 지점과 통과한 경로, 그리고 가능한 목적지가 주어졌을 때, 어떤 목적지가 실제로 통과한 경로를 거쳐서 가는 것이 최단 경로인 것인지 계산하는 문제입니다.

미확인 도착지 문제 설명입니다.

 

 

풀이 코드입니다.

import heapq
import sys
input = sys.stdin.readline
T = int(input())
INF = 1e9
total = []

for each_case in range(T):
    nodes, roads, candidates = map(int, input().split())
    departure, g, h = map(int, input().split())
    graph = [[] for _ in range(nodes+1)]
    for _ in range(roads):
        s, e, d = map(int, input().split())
        graph[s].append((e, d))
        graph[e].append((s, d))
    arrivals = [int(input()) for _ in range(candidates)]

    for e, d in graph[g]:
        if e == h:
            mustGo = d
            break

    dists = [INF]*(nodes+1)
    dists[departure] = 0
    queue = [(0, departure)]
    while queue:
        cur_dist, cur_node = heapq.heappop(queue)
        for node, dist in graph[cur_node]:
            if dists[node] > dist+cur_dist:
                dists[node] = dist+cur_dist
                heapq.heappush(queue, (dist+cur_dist, node))

    fromH = [INF]*(nodes+1)
    fromH[h] = 0
    queue = [(0, h)]
    while queue:
        cur_dist, cur_node = heapq.heappop(queue)
        for node, dist in graph[cur_node]:
            if fromH[node] > dist+cur_dist:
                fromH[node] = dist+cur_dist
                heapq.heappush(queue, (dist+cur_dist, node))

    fromG = [INF]*(nodes+1)
    fromG[g] = 0
    queue = [(0, g)]
    while queue:
        cur_dist, cur_node = heapq.heappop(queue)
        for node, dist in graph[cur_node]:
            if fromG[node] > dist+cur_dist:
                fromG[node] = dist+cur_dist
                heapq.heappush(queue, (dist+cur_dist, node))

    answer = []
    for arrival in arrivals:
        if dists[arrival] == min(dists[h]+mustGo+fromG[arrival],
                                 dists[g]+mustGo+fromH[arrival]):
            answer.append(arrival)
    answer.sort()
    total.append(answer)
for each in total:
    print(*each)

통과한 경로를 주어줄 때, 경로가 잇고 있는 두 노드가 주어집니다. 이 노드들과 시작 노드를 활용해서 총 3번 다익스트라 알고리즘을 활용하여 최단 경로를 뽑습니다. 그리고, 시작점에서 출발한 최단 경로가 중간에 통과하게 되는 노드인 g와 h를 통과한 최단 경로와 같다면, 해당 경로를 통과해서 도착하였다고 할 수 있습니다. 

 

문제를 풀면서 하나 의문이 생긴 것은, 다익스트라 알고리즘을 돌리기 위해서 최초 초기화 시 float('inf')로 하면 틀리고 큰 숫자인 1e9로 하면 맞다고 나온다.

 

나중에 생각해보니, if dists[arrival] == min(dists[h]+mustGo+fromG[arrival], dists[g]+mustGo+fromH[arrival]) 부분에서, float('inf')에 상수를 더해도 float('inf')가 나오기 때문에 도착할 수 없는 목적지 후보가 존재하더라도 일치한다고 나와서 그런 것 같다. 그냥 큰 상수를 집어넣을 경우, 일치한다고 나오기 때문이었다. 실제로, 해당 조건문에 dists[arrival] != INF 조건을 추가하자, 문제가 풀이되는 것을 볼 수 있었다. 

 

다음은 풀이 결과입니다.