[BOJ] 9370번 미확인 도착지 / 사용언어 : 파이썬(python)

※ 문제링크

9370번: 미확인 도착지

※ 관련개념

23. 다익스트라(Dijkstra) 알고리즘

해당 문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 문제에서 주어진 시간 조건과 메모리 조건이 생각보다 여유롭다고 판단하여 BOJ 1504번에서 사용했던 개념을 그대로 가져와 살짝 변형하여 해결코드를 구현하였고, 테스트 결과 정상적으로 작동하는 것을 확인하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 딕셔너리를 활용하여 그래프를 구현하고, 최단거리를 저장(메모이제이션 적용)할 리스트를 생성한다.

2. heapq로 다익스트라 알고리즘을 구현하고, 출발점에서 각 정점으로 갈 수 있는 최단거리를 구할 함수를 작성한다.

3. 문제조건상 g, h를 반드시 경유해야 하므로, 각각의 정점을 경유했을 때의 최단거리를 구할 함수를 작성한다.
(s → g → h → dt와 s → h → g → dt의 값을 모두 구한 후 최소값을 반환하는 함수) 

4. 시작지점에서 다익스트라 함수를 적용한 dp값과 경유했을 때의 최단거리가 같을 경우 ans에 추가한다.
(inf와 일치여부를 반드시 확인하고, 해당 값이 inf가 아닐경우에만 추가해야함)

5. ans를 오름차순으로 정렬 후 결과값을 출력한다.
+ 시간 및 메모리 최적화를 위해 sys를 사용하였습니다. sys사용시에는 반드시 개행문자에 유의하도록 합시다.

 

import sys
import heapq

def dijstra(start):
    dp = [float('inf') for _ in range(n+1)]
    heap = []
    dp[start] = 0
    heapq.heappush(heap, [0, start])
    
    while heap:
        wei, cp = heapq.heappop(heap)
        for cp_n in graph[cp]:
            wei_cp, cp_cp = cp_n[0], cp_n[1]
            check_wei = wei + wei_cp
            if check_wei < dp[cp_cp]:
                dp[cp_cp] = check_wei
                heapq.heappush(heap, [dp[cp_cp], cp_cp])

    return dp

def min_distance(start, cp1, cp2, dt):
    distance1 = distance_dic[start][cp1] + distance_dic[cp1][cp2] + distance_dic[cp2][dt]
    distance2 = distance_dic[start][cp2] + distance_dic[cp2][cp1] + distance_dic[cp1][dt]
    return min(distance1, distance2)

T = int(input())
# T = int(sys.stdin.readline())
for _ in range(T):
    n, m, t = map(int, input().split()) # n: 교차로 수(정점) / m: 도로 수(간선) / t: 목적지 후보의 개수
    # n, m, t = map(int, sys.stdin.readline().split()) # n: 교차로 수(정점) / m: 도로 수(간선) / t: 목적지 후보의 개수
    s, g, h = map(int, input().split()) # s: 출발지점 / g, h : 반드시 지나야하는 경로 
    # s, g, h = map(int, sys.stdin.readline().split()) # s: 출발지점 / g, h : 반드시 지나야하는 경로 
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, d = map(int, input().split()) # a, b : 서로 이어진 정점(양방향) / d : 간선의 가중치
        # a, b, d = map(int, sys.stdin.readline().split()) # a, b : 서로 이어진 정점(양방향) / d : 간선의 가중치
        graph[a].append([d, b])
        graph[b].append([d, a])

    distance_dic = dict()
    ans = []
    distance_dic[s] = dijstra(s)
    distance_dic[g] = dijstra(g)
    distance_dic[h] = dijstra(h)
    for _ in range(t):
        dt = int(input())
        # dt = int(sys.stdin.readline())
        distance_dic[dt] = dijstra(dt)
        if min_distance(s, g, h, dt) == distance_dic[s][dt] and distance_dic[s][dt] != float('inf'):
            ans.append(dt)
    ans.sort()
    print(*ans)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.