[ Python ] BOJ // Q9370 - 미확인도착지

최근 여러 알고리즘 문제들을 풀어보며 안 풀리는 문제는 검색해가며 풀어보고 있습니다.

그중에서 한 분의 코드 리뷰에서 단순히 이렇게 풀었다. 라기보다 누구에게 상세히 설명하듯이 설명해 둔 코드 리뷰를 보고 지금껏 작성해왔던 코드 리뷰들이 과연 다른 사람이 보았을 때 잘 읽히는 코드 리뷰였을까?라는 생각이 들었습니다.

앞으로는 내가 보기 위한 글이면서 동시에 남이 보기에도 잘 읽히는 코드 리뷰를 작성할 수 있도록 노력해보려 합니다.

https://www.acmicpc.net/problem/9370

오늘의 리뷰 문제는 9370 미확인 도착지입니다.우선 주어지는 각각의 변수들은 다음과 같습니다.

T 테스트 케이스의 수 ( 100 이하의 자연수 )
1. 첫 번째 줄에 3개의 정수가 주어집니다. n(교차로 수), m(도로 수), t(목적지 후보의 개수)
  ( 2 <= n <= 2,000 // 1 <= m <= 50,000 // 1 <= t <= 100 )
2. 두 번째 줄에도 3개의 정수가 주어집니다. s(출발 노드), g, h (반드시 거쳐가는 도로 g-h)
3. 그다음 m 개의 줄에 a, b, d (a에서 b 사이의 길이 d의 간선이 존재한다.)
4. 그다음 t 개의 줄에 목적지 후보군 한 개의 정수 x 가 주어지며 중복되지 않습니다.
5. 교차로 사이에 간선은 1개 이하입니다. 동시에 g-h의 간선은 무조건 존재합니다.
  그 간선은 최소 1개 이상의 목적지로 향하는 최단경로입니다.

WHAT? 무엇을 사용해야 하는가?

이 문제에서 주목해야 할 점은 후보 노드 중에서 g-h 간선이 최단노선에 포함되는 노드만을 추려내야 하는 점입니다.

그래프에서 최단경로를 구하는 가장 흔한 알고리즘은 ( 다익스트라 알고리즘, 플로이드 워셜 )을 꼽을 수 있을 듯합니다.
각 알고리즘의 세부 내용은 오늘 다루지 않겠습니다.

그렇다면 이번 문제에서 사용해야 할 그래프 알고리즘은 무엇일까요?

이미 주어진 변수들에서 교차로(노드) n의 수가 최대 2000 개 이므로 O(N^3)의 시간 복잡도를 필요로 하는 플로이드 워셜 알고리즘은 어렵습니다. 따라서 다익스트라 알고리즘을 사용해야 한다는 사실을 알게 되었습니다.

HOW? 어떻게 풀어야 하는가?

다익스트라 알고리즘은 특정 노드에서 모든 노드까지의 최단거리를 반환합니다.
하지만 오늘 구해야 할 값은 시작 노드에서 후보군까지 가는 최단경로에 g-h 가 포함되어있는가?입니다.

저의 첫 풀이 구상은 거리 테이블의 원소를 거리 dist 하나가 아닌 [ dist , bool ]로 바꾸어 g-h 만 bool 값을 True로 주는 가중 방법을 사용하고자 했습니다. 하지만 시간 초과와 더불어 오답 판정을 받았습니다.
( 하지만 이런 가중치 방법으로 풀어낸 사람이 있는 것으로 보아선 예외처리의 실수 때문인 듯합니다. )

실제로 사용된 두 번째 풀이 구상은 S to T의 최단경로에 G-H 가 포함되는 것이 참이라면, (S to G의 최단거리) + (G to H의 최단거리) + (H to T의 최단거리)와 같이 S에서 G, H를 최단거리로 경유하여 T에 도착하는 경로 값이 S to T의 직접 최단거리 값과 같을 것이라는 방법입니다.

위 구상을 구현하기 위해 필요한 값은 다음과 같습니다.

S에서
1. T까지의 최단거리
2. G까지의 최단거리
3. H까지의 최단거리
G에서
1. H까지의 최단거리
2. T까지의 최단거리
H에서
1. G까지의 최단거리
2. T까지의 최단거리

따라서 S, G, H 세 점에서 시작하는 다익스트라 알고리즘 반환 값을 구한다면 문제없이 풀어낼 수 있을 것입니다.
또한 우선순위 큐를 이용한 개선 알고리즘을 사용한다면, 그 시간 복잡도는 MLogN 이므로 시간제한 또한 문제없이 통과할 수 있을 것입니다.

// CODE // 풀이에 사용된 코드

import heapq
hpush = heapq.heappush
hpop = heapq.heappop

T = int(input())

for _ in range(T):

    n,m,t = map(int,input().split())
    s,g,h = map(int,input().split())
    s,g,h = s-1,g-1,h-1

    data = [[] for _ in range(n)] #간선데이터
    ghdist = 1e9
    
    for _ in range(m):
        a,b,d = map(int,input().split())
        a,b,d = a-1,b-1,d
        if [a,b] in [[g,h],[h,g]]:
            ghdist = min(ghdist,d)
        data[a].append([d,b])
        data[b].append([d,a])
    
    dest = [] #목적지 후보군
    for _ in range(t):
        dest.append(int(input()))

    def dijkstra(start):
        dist = [1e9]*n
        q = [[0,start]]
        dist[start] = 0
        while q:
            nowdist, node = hpop(q)
            if dist[node] < nowdist:
                continue
            for nextdist,nextnode in data[node]:
                if dist[nextnode] > dist[node] + nextdist:
                    dist[nextnode] = dist[node] + nextdist
                    hpush(q,[dist[nextnode],nextnode])
                    
        return dist #다익스트라 알고리즘을 통해 최단거리배열이 반환된다.
        
    #다익스트라 알고리즘을 통한 s,g,h 노드의 최단거리 배열들
    db_s = dijkstra(s)
    db_g = dijkstra(g)
    db_h = dijkstra(h)
    
    res = []
    
    for i in dest:
        i -= 1
        
        # (s to h to g to i) == s to i 혹은 (s to g to h to i) == s to i 를 만족하는가
        if db_s[g]+db_g[h]+db_h[i] == db_s[i] or db_s[h]+db_h[g]+db_g[i] == db_s[i]:
            res.append(i+1)
    res.sort()

    for f in res:
        print(f, end=' ')
    print()