백준 9370번: 미확인 도착지 (Python)

접근

바로 이전에 풀었던 다익스트라 알고리즘 문제에 추가적인 알고리즘을 더하여 해결할 수 있다.

다익스트라 알고리즘 기본 문제: 2021.04.14 - [코딩/백준 (Python)] - 백준 1753번: 최단경로 (Python)

백준 1753번: 최단경로 (Python)

문제를 해결하는 방법에는 두가지 정도의 방법이 있고 이는 다음과 같다.

1. start - g - h - end 루트나 start - h - g - end 루트를 계산하여 start - end 루트와 비교하기
2. start - end 루트 다익스트라 연산 때 g - h 루트에 추가 보정해주기

첫 번째 방법으로 문제를 해결할 때에는 start, g, h 에서 출발하는 다익스트라 연산을 해주어야 하기 때문에 총 3번의 연산이 필수적이다. 두 번째 방법으로는 다익스트라 연산 한번으로 해결할 수 있기 때문에 두번째 방법으로 시도해보았다. 그 중에 생각보다 매우 쉽게 문제를 해결할 방법이 떠올라 소개해보려고 한다.

g - h 루트를 저장할 때 가중치에 0.1을 빼주는 것이다. 이 작업으로 얻을 수 있는 장점은 두가지가 있다.

1. 가중치가 같은 g - h 를 지나지 않는 루트보다 0.1 만큼 작기 때문에 g - h 를 지나는 루트가 더 작아져 알고리즘의 선택을 받게 된다.
2. g - h 를 지나는 길은 목적지에서 저장된 가중치가 int 타입이 아닌 float 타입이기 때문에 구분하기가 쉽다.

start 지점에서 시작하는 다익스트라 알고리즘 연산을 한번 수행하고, 목적지를 한번씩 탐색하면서 이 값이 무한값이 아니고(목적지에 도착할 수 있고), float 타입을 가지면(g - h 루트를 지나면) 해당 목적지로 예술가가 이동함을 알 수 있다.

코드

import sys
import heapq


def Dijkstara(start):
    visited = [float('inf') for _ in range(v + 1)]
    visited[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    while heap:
        weight, now = heapq.heappop(heap)
        if visited[now] < weight:
            continue
        for w, n in lines[now]:
            nw = w + weight
            if nw < visited[n]:
                visited[n] = nw
                heapq.heappush(heap, (nw, n))
    return visited


for _ in range(int(sys.stdin.readline())):
    v, m, t = map(int, sys.stdin.readline().split())
    s, g, h = map(int, sys.stdin.readline().split())
    lines = [[] for __ in range(v + 1)]
    for __ in range(m):
        a, b, d = map(int, sys.stdin.readline().split())
        if (a == g and b == h) or (a == h and b == g):
            lines[a].append([d - 0.1, b])
            lines[b].append([d - 0.1, a])
        else:
            lines[a].append([d, b])
            lines[b].append([d, a])
    target = []
    for i in range(t):
        target.append(int(sys.stdin.readline()))
    ans = []
    sr = Dijkstara(s)
    for tar in target:
        if sr[tar] != float('inf') and type(sr[tar]) == float:
            ans.append(tar)
    ans.sort()
    print(*ans)

더 생각해 볼 것?

다익스트라 연산 한번에 해결할 방법을 이리저리 찾다가, 모든 루트의 가중치가 0이고 g - h 루트의 가중치만 1인 추가적인 가중치를 추가해보기도 하였다. 하지만 같은 가중치를 가진 또다른 루트 존재 문제 해결하기 위해서는 코드가 많이 길어졌지만, 이 방법은 코드 수정 거의 없이 간단하게 구현되어 깔끔하게 해결되었다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!