코드

import heapq
INF = int(1e9)

for _ in range(int(input())):

    # n : 교차로의 개수
    # m : 도로의 개수
    # t : 목적지 후보의 개수
    n, m, t = map(int, input().split())

    # s : 예술가들의 출발지
    # g, h : 예술가들이 지나간 도로
    s, g, h = map(int, input().split())

    # 도로의 간선 및 가중치 정보를 담을 리스트
    graph = [[] for _ in range(n+1)]

    # 도로 정보 입력
    for _ in range(m):
        a, b, d = map(int, input().split())

        graph[a].append((b, d))
        graph[b].append((a, d))

    # 목적지 후보를 담을 리스트
    destinations = []

    for _ in range(t):
        destinations.append(int(input()))

    # 다익스트라 구현
    def dijkstra(start):
        q = []
        heapq.heappush(q, (0, start))

        # 최단 거리 테이블
        dist_table = [INF for _ in range(n+1)]
        dist_table[start] = 0

        while q:
            # w : v까지 오는데 드는 가중치, v : 현재 방문 노드
            w, v = heapq.heappop(q)

            if w > dist_table[v]:
                continue

            # 위의 조건식으로 인해서
            # 아래 코드에선 w가 무조건 dist_table[v]보다 작음
            # (INF로 초기화 돼있으므로 같을 이유도 없음)
            for i in graph[v]:

                # i[0] : 현재 노드 v에서 다음으로 이동할 노드
                # i[1] : i[0]로 이동할 때 드는 가중치
                # cost : 이전까지의 이동 가중치 + i[0]로 가는 가중치
                cost = w + i[1]

                if cost < dist_table[i[0]]:
                    dist_table[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))

        # 출발 지점마다 최단 거리를 구해야 하므로 
        # 최단 거리 테이블을 각각 리턴해줌
        return dist_table

    # 시작, g, h에서 각각 다익스트라 수행
    tot = dijkstra(s)
    part1 = dijkstra(g)
    part2 = dijkstra(h)
    
    # 최종 경로를 담을 리스트
    result = []
    
    for d in destinations:
        # 1. s -> g -> h -> destination 최단 경로
        # 2. s -> h -> g -> destination 최단 경로
        # 위 두 경로 중 어느 하나라도
        # s -> destination의 최단 경로와 같다면 result에 저장
        if tot[g] + part1[h] + part2[d] == tot[d] or tot[h] + part2[g] + part1[d] == tot[d]:
            result.append(d)
    
    result.sort()
    
    for r in result:
        print(r, end = ' ')
    print() # 테스트마다 출력을 보기 위한 줄바꿈

문제 해설

다익스트라 알고리즘을 사용한 최단 경로를 구하는 문제.

이 문제의 경우, 지문 자체를 이해하는 것이 풀이를 하는 것보다 어려울 정도로 문제 풀이 방식 자체는 특정한 최단 경로 문제와 별 차이가 없다. 단, 앞서 언급한 것처럼 지문에 대한 이해가 매우 중요하다.

문제의 요구 사항을 정리하면 아래와 같다.

  1. 노드 g, h 사이에 존재하는 도로는 무조건 지나가야 함
    • 시작 -> g -> h -> 목적지
    • 시작 -> h -> g -> 목적지
    • 위 둘 중 하나의 경로로 이동
  2. 예술가는 항상 목적지에 최단 경로로 이동함
    • 즉, 1번의 경로는 s -> 목적지로 바로 가는 최단 경로와 동일해야함

위의 요구 사항 중 2번을 파악하는 것에 애를 먹었다 ㅠㅠ 사실상 2번만 알게 된다면 문제 자체는 구간 별로 다익스트라 알고리즘을 적용하고 결과를 오름차순으로 정렬하여 출력시키면 된다.

다른 문제들도 마찬가지지만 최단 경로 알고리즘의 경우 알고리즘을 확실하게 구현해놓으면 훨씬 문제 풀이에 쉽게 접근할 수 있는 것 같다.

댓글남기기

참고