[백준 9370 파이썬] 미확인 도착지 (골드2, 다익스트라)

알고리즘 유형 : 다익스트라
풀이 참고 없이 스스로 풀었나요? : X

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

SOLVE 1

특정 도로를 거치고 가는 최단 거리와, 조건 없이 가는 최단 거리를 비교하여 진위를 가리는 풀이(다익스트라 3번 실행)

import sys
import heapq
input = sys.stdin.readline


# 다익스트라 알고리즘
def dijkstra(start):
    route = [float("inf")]*(n+1)
    route[start] = 0
    q = [(0, start)]
    
    while q:
        cnt_route, cnt_node = heapq.heappop(q)
        
        if route[cnt_node] < cnt_route:
            continue
            
        for adjacency_node, adjacency_route in road[cnt_node].items():
            cal_route = route[cnt_node] + adjacency_route
            
            if cal_route < route[adjacency_node]:
                route[adjacency_node] = cal_route
                heapq.heappush(q, (cal_route, adjacency_node))
    
    return route



T = int(input())
for _ in range(T):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())
    road = [{} for _ in range(n+1)]
    candidate = []
    
    for i in range(m):
        a, b, d = map(int, input().split())
        
        # (도로 길이, 교차로)
        road[a][b] = d
        road[b][a] = d
        
    for i in range(t):
        candidate.append(int(input()))
    
    # 출발 교차로부터 모든 교차로까지의 최단 거리 구함
    s_dijk = dijkstra(s)
    
    # s에서 g까지의 최단거리, h까지의 최단거리
    s_to_g = s_dijk[g]
    s_to_h = s_dijk[h]
    
    # g에서 h, h에서 g까지의 최단 거리는 그 둘 사이의 도로 길이와 같으므로
    # road 변수 단순 인덱싱하기(이를 위해 road를 딕셔너리로 할당했음)
    g_to_h = road[g][h]
    h_to_g = road[h][g]
    
    # h, g에서 모든 교차로까지의 최단 거리 구함
    # 리턴값중에서 후보군까지의 최단 거리를 인덱싱하여 활용할거임
    h_to_c = dijkstra(h)
    g_to_c = dijkstra(g)
    
    result = ""
    # 각 목적 교차로 후보군을 순회하면서, 그 목적 교차로까지 조건 없이 가는 최단 거리와
    # h, g를 거치고 가는 최단 거리를 비교하여 진위를 결정
    for c in sorted(candidate):
        path1 = s_to_g + g_to_h + h_to_c[c]
        path2 = s_to_h + h_to_g + g_to_c[c]
        
        route_gh, route_all = min(path1, path2), s_dijk[c]
        if route_gh != float("inf") and route_gh == route_all:
            result += str(c) + " "
            
    print(result)

SOLVE 2

g-h 도로 길이에 -0.1을 해준 뒤, 목적 교차로 후보까지의 조건없는 최단 거리를 구하고 그 값이 실수형인지 정수형인지로 진위를 따지는 풀이(다익스트라 1번 실행)

import sys
import heapq
input = sys.stdin.readline


# 다익스트라 알고리즘
def dijkstra(start):
    route = [float("inf")]*(n+1)
    route[start] = 0
    q = [(0, start)]
    
    while q:
        cnt_route, cnt_node = heapq.heappop(q)
        
        if route[cnt_node] < cnt_route:
            continue
            
        for adjacency_node, adjacency_route in road[cnt_node].items():
            cal_route = route[cnt_node] + adjacency_route
            
            if cal_route < route[adjacency_node]:
                route[adjacency_node] = cal_route
                heapq.heappush(q, (cal_route, adjacency_node))
    
    return route



T = int(input())
for _ in range(T):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())
    road = [{} for _ in range(n+1)]
    candidate = []
    
    for i in range(m):
        a, b, d = map(int, input().split())
        
        # (도로 길이, 교차로)
        road[a][b] = d
        road[b][a] = d
        
    for i in range(t):
        candidate.append(int(input()))
    
    # 반드시 거치는 도로에 -0.1해주기.
    # 만약 변형 전에, 이 도로를 거치는 경로가 최단 경로였다면,
    # 오히려 더 거리가 짧아진 것이므로 최단 경로는 그대로임
    # 만약 변형 전에, 이 도로를 거치는 경로가 최단 경로가 아니였다면,
    # 만약 다른 경로가 이 도로를 거치는 경로보다 1 작았다면
    # 변형 후에도 0.9가 작으므로 최단 경로는 유지됨
    # 즉, 0.1을 빼줘도 원래의 최단 경로는 변하지 않으므로 괜찮음
    # 만약 최단 거리가 실수형이면 g-h 도로를 거쳤다는 것을 의미함
    road[g][h] -= 0.1
    road[h][g] -= 0.1
    
    route_s = dijkstra(s)
    
    result = ""
    for c in sorted(candidate):
        route_s_to_c = route_s[c]
        
        if route_s_to_c != float("inf") and type(route_s_to_c) == float:
            result += str(c) + " "
            
    print(result)

SOLVE 1) 풀이 요약 (특정 도로를 거치고 가는 최단 거리와, 조건 없이 가는 최단 거리를 비교하여 진위를 가리는 풀이(다익스트라 3번 실행))

1. 해당 문제는 이해하는 데 조금 어려움이 있을 수 있다. 문제에서 구하고자 하는 바는 듀오의 목적지인데, 듀오는 반드시 최단 경로로 이동한다. 그런데 g-h 도로를 지나치는 것을 우리는 목격했고, 우리는 목적지 후보군으로 가는 모든 최단거리들에 대해 g-h 도로가 루트에 포함되어 있는지를 확인하여 듀오가 가는 목적지들을 새로 추려내는 것이 목적이다.

2. 이를 위해 다익스트라 알고리즘을 총 3번 실행한다. 우선 출발지에서 한 번, h에서 한 번, g에서 한 번 실행하면 된다.

   이렇게 다익스트라를 호출해서, 모든 노드까지의 최단거리를 담은 리스트를 리턴해서 받으면 된다.

   임의의 후보 목적지 하나에 대해, 출발지에서 목적지까지의 최단 거리와, 출발지 -> g -> 목적지, 출발지 -> h -> 목적지 거리 중 더 짧은 값을 비교하여 만약 같다면 듀오는 해당 후보 목적지로 갈 수도 있는, 새로운 후보군이 된다.

   다익스트라로 구해서 리턴받은 리스트를 인덱싱해서 값을 비교해주면 된다.

SOLVE 2 풀이 요약 (g-h 도로 길이에 -0.1을 해준 뒤, 목적 교차로 후보까지의 조건없는 최단 거리를 구하고 그 값이 실수형인지 정수형인지로 진위를 따지는 풀이(다익스트라 1번 실행))

1. 이 풀이는 g-h 도로의 가중치를 실수형으로 만든 뒤, 출발지로부터 모든 목적지 후보군까지의 최단 거리를 구한 뒤, 그 값이 실수인 어떤 목적지가 있다면, 그 특정 목적지까지의 최단 거리 루트에 g-h 도로가 포함되어 있다는 뜻이고, 따라서 그 목적지가 듀오가 현재 도달가능한 새로운 목적지 후보군임을 활용한 풀이이다.

2. g-h 도로의 길이를 실수형으로 조작하고, 출발점에서 모든 노드까지의 최단 거리를 구하므로, 다익스트라를 한 번만 호출하면 된다.

3. 그렇다면 g-h 도로 길이를 실수형으로 만들기 위해 -0.1을 해주어도, 실제 최단 경로는 변하지 않는지 확인해보자.

   특정 목적지에 대해, 만약 변형 전에 이 도로를 거치는 경로가 원래 최단 경로였다면, 오히려 0.1 더 짧아지는 것이므로 변형 하고나서도 똑같이 최단 경로다.

   만약 변형 전에 이 도로를 거치는 경로가 원래 최단 경로가 아니었다면, 길이를 변형한 도로 말고 다른 특정 도로가 최단 경로일텐데, 두 도로 간의 길이 차이가 1밖에 안난다고 치자. 그렇다고 해도 0.1만 줄였기 때문에 길이의 대소 관계는 변하지 않는다. 따라서 원래의 최단 경로는 그대로 유지된다.

   즉, g-h 도로 길이에 0.1을 빼줘도 최단 경로는 원래 그대로 유지되므로, 다익스트라로 구한 최단 경로가 실수형인지 확인하여 그 루트에 g-h 도로가 포함되어 있는지를 판별하는 방법은 유효하다.

배운 점, 어려웠던 점

• 문제를 이해하는게 어려웠다. 잘못 이해해서 엉뚱한 방법으로 풀었다... 제대로 이해했다면 1번 풀이는 무리없이 해냈을 것 같은데 2번 풀이는 생각도 못했을 것 같다. 참신한 다익스트라 응용을 경험할 수 있어 유익한 문제였다.