[Python] 백준 #9370 미확인 도착지

📚문제: #9370 미확인 도착지(Gold 2)

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

• 첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
  
  
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
  
  
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
  
  
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.
  
  교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

예제 입력 1

2
5 4 2
1 2 3
1 2 6
2 3 2
3 4 4
3 5 3
5
4
6 9 2
2 3 1
1 2 1
1 3 3
2 4 4
2 5 5
3 4 3
3 6 2
4 5 4
4 6 3
5 6 7
5
6

예제 출력 1

4 5
6

아이디어 및 구현

• 시작노드(s)에서 목적지 후보노드까지 최소비용 경로에 (g-h) 간선이 포함되는지 확인한다.

• (g-h) 간선의 비용은 따로 저장한다.

# a와 b사이 길이 d인 양방향 도로
a, b, d = map(int, sys.stdin.readline().split())

if (a == g and b == h) or (a == h and b == g):

    edge = d

• 시작지점 s와 거쳐가는 지점 g, h에서 각각 Dijkstra Algorithm을 수행해준다.
  • 최소비용경로 = min(cost(s→g→h→end), cost(s→h→g→end))

    # Dijsktra Algorithm
    Dijkstra(s, distance_s)
    Dijkstra(g, distance_g)
    Dijkstra(h, distance_h)

    # 답안 노드
    ans = []

    for node in candidate:
		
        # 시작 ~ 목적지 까지 비용 계산, 아래 두 값중 최소값을 선택
        # (g-h) 간선을 반드시 거쳐가는 경로이다.
        total = min(distance_s[g] + edge + distance_h[node], distance_s[h] + edge + distance_g[node])
		
        # 두 값이 같으면 (g-h) 간선이 포함된 것으로 봐도 됨
        if total == distance_s[node]:

            ans.append(node)

전체 코드

import sys
from heapq import heappush, heappop

# INFINITY
INF = int(1e10)

# Dijkstra Algorithm
def Dijkstra(start, distance):

    # 우선순위 큐
    q= []

    # 출발지 처리
    distance[start] = 0

    heappush(q, (0, start))

    while q:

        dist, cur = heappop(q)

        if dist > distance[cur]:

            continue
        
        # 이웃 노드까지 가는 비용을 조사
        for neighbor in graph[cur]:

            # cur를 거쳐서 neighbor[0]까지 가는 비용
            cost = dist + neighbor[1]

            # 더 작다면 갱신
            if cost < distance[neighbor[0]]:

                distance[neighbor[0]] = cost

                heappush(q, (cost, neighbor[0]))
  
# 테스트 케이스 T
T = int(sys.stdin.readline().rstrip())

# 각 테스트케이스에 대해서 수행
for _ in range(T):

    # n: 교차로, m: 도로, t: 목적지 후보
    n, m, t = map(int, sys.stdin.readline().split())

    # 그래프 생성 (1 ~ n)
    graph = [[] for _ in range(n+1)]

    # 최단거리 list
    distance_s = [INF] * (n+1)
    distance_g = [INF] * (n+1)
    distance_h = [INF] * (n+1)

    # s: 예술가들의 출발지, g와 h 교차로 사이에 있는 도로를 지나감.
    s, g, h = map(int, sys.stdin.readline().split())

    # m개의 각 줄마다 3개의 정수가 주어진다.
    for _ in range(m):

        # a와 b사이 길이 d인 양방향 도로
        a, b, d = map(int, sys.stdin.readline().split())

        if (a == g and b == h) or (a == h and b == g):

            edge = d
        
        # 그래프 반영
        graph[a].append((b,d))
        graph[b].append((a,d))
    
    # 정수 x가 주어진다. t개의 목적지 후보
    candidate = []
    for _ in range(t):

        candidate.append(int(sys.stdin.readline().rstrip()))
    
    # Dijsktra Algorithm
    Dijkstra(s, distance_s)
    Dijkstra(g, distance_g)
    Dijkstra(h, distance_h)

    # 답안 노드
    ans = []

    for node in candidate:

        total = min(distance_s[g] + edge + distance_h[node], distance_s[h] + edge + distance_g[node])

        if total == distance_s[node]:

            ans.append(node)
    
    ans.sort()

    print(*ans)

TIL

첫 시도에서는 시작노드(s)에서 목적지 노드까지 최소비용으로 도달하는 경로를 따로 저장하고 (g-h) 간선이 해당 경로에 포함되는지 확인하는 방식으로 작성하였다.

하지만 최소비용 경로가 여러개 존재하는 테스트 케이스에 대해 올바르게 작동하지 않아 위와 같이 코드를 수정하였다.

최소비용경로에 특정 간선이 포함되는지 여부를 확인하기 위해서는 전체경로를 작은 부분으로 나누어서 판단할 필요가 있다.