[🥇2 / 백준 9370 / 파이썬] 미확인 도착지

 

9370번: 미확인 도착지

 

문제

(취익)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개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

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

예제 입력  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

예제 출력  4 5 6

 

풀이

 

다익스트라 응용문제이다.

다익스트라에 대한 사전 지식이 없다면 아래의 포스팅을 참고하길 바란다.

 

[백준 1753 / 파이썬] 최단경로

 

문제에서 확실히 짚고 넘어가야 할 것이 있다.

예술가들은 자신들이 설정한 목적지까지 '반드시 최단 경로로만 이동'한다는 것이다.

 

 

위 그림에서 1-3 경유지를 지나고 난 뒤, 6은 물론 5에도 갈 수 있다.

단, 5가 답이 될 수 없는 이유는 만약 5로 가려 했다면 1-3 경유지를 지날 이유가 없다는 것이다.

바로 2-5로 이동하는 것이 최단 경로이기 때문이다.

 

 

한편, 위와 같은 모든 간선의 가중치가 1인 그래프가 있다고 가정해보자.

시작점에서 정점 1과 2 모두 거리가 같기 때문에 아무 간선으로나 갈 수 있게 된다.

 

구하고자 하는 답은 5, 6 이지만 경우에 따라 3, 4가 답이 될 수도 있다는 말이다.

 

따라서 우리는 다익스트라를 진행한 뒤 해당 정점까지의 경로에 g-h 혹은 h-g 가 있었는지 체크할 필요가 있다.

 

 

여기 굉장한 아이디어가 있다. (필자의 아이디어는 아니다.)

 

모든 간선에 2를 곱한 뒤, g-h(h-g) 간선에만 -1을 하여 홀수를 만들어주는 것이다.

그렇다면 g-h 간선을 지나온 최단 경로들만 홀수가 된다.

또한 -1을 하였기 때문에 위의 그림처럼 같은 가중치의 간선과 마주하더라도

무조건 g-h 경로 쪽을 우선으로 탐색하게된다.

 

import heapq, sys
input = sys.stdin.readline

def djikstra(start):
        dist = [float('inf')] * n
        dist[start] = 0
        heap = [(0,start)]

        while(heap):
            curDist, curNode = heapq.heappop(heap)

            if dist[curNode] < curDist:
                continue

            for toNode,toDist in linked[curNode]:
                d = curDist + toDist
                if dist[toNode] > d:
                    dist[toNode] = d
                    heapq.heappush(heap,(d,toNode))
        return dist
    
for i in range(int(input())):
    n,m,t = map(int,input().split())
    s,g,h = map(int,input().split())
    s-=1; g-=1; h-=1

    # 인접 리스트 생성.
    # g-h(h-g) 간선에만 -1을 하여 홀수로 만들어준다.
    linked = [[] for i in range(n)]
    for i in range(m):
        a,b,d = map(int,input().split())
        if (a-1,b-1) == (g,h) or (a-1,b-1) == (h,g):
            linked[a-1].append((b-1,d*2-1))
            linked[b-1].append((a-1,d*2-1))
            continue
        linked[a-1].append((b-1,d*2))
        linked[b-1].append((a-1,d*2))

    # 후보 정점
    cand = []
    for i in range(t):
        cand.append(int(input())-1)
    cand.sort()

    r = djikstra(s)

    # 최단 경로가 홀수인 경우에만 g-h(h-g) 간선을 지나온 것이므로
    # 홀수인 정점들만 출력해준다.
    for i in cand:
        if r[i]%2 == 1:
            print(i+1,end=" ")