[BOJ][Python]9370 풀이

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

9370번: 미확인 도착지

import heapq
import sys
ssr = sys.stdin.readline

INF = 2000001

def dijkstra(start, end=None):
    h = [(0, start)]
    min_dist = [INF for _ in range(n+1)]
    min_dist[start] = 0
    while h:
        cur_dist, cur_node = heapq.heappop(h)
        if cur_dist > min_dist[cur_node]:
            continue
        for next_dist, next_node in routes[cur_node]:
            dist = min_dist[cur_node] + next_dist
            if dist < min_dist[next_node]:
                min_dist[next_node] = dist
                heapq.heappush(h, (min_dist[next_node], next_node))
    if end == None:
        return min_dist
    else:
        return min_dist[end]

c = int(ssr())
for _ in range(c):
    n, m, t = map(int, ssr().split())
    s, g, h = map(int, ssr().split())
    routes = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, d = map(int, ssr().split())
        if (a == h and b == g) or (a == g and b == h):
            d -= 0.1
        routes[a].append((d, b))
        routes[b].append((d, a))
    distance = dijkstra(s)
    ans = []
    for _ in range(t):
        x = int(ssr())
        if type(distance[x]) != int:
            ans.append(x)
    print(*sorted(ans))

오늘은 문제가 한 눈에 안들어와서 이해하는데에 좀 시간이 걸렸습니다. 제 나름대로 문제를 쉽게 고쳐 쓰면,

'g 노드와 h 노드를 연결하는 간선을 지나는 경로가 최단 거리인 경우를 목적지 후보 중에서 오름차순으로 출력해라' 정도로 고쳐쓸 수 있을 것 같아요. 도로는 양방향성이고 동일 노드를 연결하는 간선은 없거나 하나 뿐입니다.

 

처음에는 이런 필수 경로를 지나게하는 문제를 전에 풀어봤던지라 그 때처럼 데이크스트라를 3번 사용하는 코드를 짰었는데 정말 겨우겨우 통과하길래 더 좋은 방법이 있나 싶어서 혼자 고민을 했는데 잘 모르겠더라구요. 그래서 다른 분들 코드를 봤는데 정말 좋은 풀이를 찾아서 해당 방법으로 알려드릴까 합니다.

 

입력을 받을 때 필수 경로라면 해당 경로의 길이를 약간 줄여서 받는 테크닉을 사용합니다. 이게 상당히 좋은 테크닉인게 최단거리인 경로가 여러 개가 입력으로 들어오는 경우가 있는데 특정 경로를 지났는지 안지났는지 판단해서 출력하려면 데이크스트라를 진행하면서 간선 정보를 확인할 때 마다 조건문으로 확인을 해주어야 하는데 이렇게 필수경로를 아주 조금 줄여서 받으면 최단거리를 갖는 경로가 오로지 필수 경로를 지나치는 경우로 한정되게 됩니다.

 

아예 필수 경로를 지나치는 경우가 최단거리가 아닌 경우도 입력으로 들어오는데 이럴 경우에는 필수 경로를 지나치는 경우의 최단거리를 구하고 아닐 경우의 최단거리를 각각 구해서 비교하는 방법이 필요한데 이렇게 소수점으로 아주 작게 줄였을 경우는 마지막에 최단 경로의 데이터 타입이 정수형인지 실수형인지 비교하는 걸로 필수 경로를 지나쳤는지 확인이 가능합니다.

 

물론 이 방법은 거리가 정수로 들어온다는 전제 조건이 있기 때문에 가능한 것인데 정말 간단한 방법으로 데이크스트라를 사용하는 횟수를 획기적으로 줄였습니다. 세상엔 정말 번뜩이는 아이디어를 가진 분들이 많은 것 같아요.

 

데이크스트라에 대해 좀 더 궁금하시다면,

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드