[알고리즘 문제 풀이][파이썬] 백준 9370번: 미확인 도착지

백준 9370번 문제 링크: https://www.acmicpc.net/problem/9370

📑 문제 설명

최단 경로인 다익스트라 알고리즘으로 푸는 문제이다. 핵심은 s에서 시작해서 g, h를 지나가는 간선이 최단 경로에 포함이 되는지, 되지 않는지 체크해야 한다. 즉, s에서 시작해서 목표인 t로 갈 때 g-h or h-g를 지나가면 출력, 아니면 출력하지 않는다.
입력: test case 수/n,m,t(node 수, 간선 수, 목표 지점 수)/s,g,h(시작점, 지나간 지점)/a,b,d(a와 b가 이어져있으며 거리는 d)/t(목표지점)
출력: s,g,h를 지나치는 최단경로로 도착할 수 있는 목표 노드

💡 문제 해결 방법

• 다익스트라를 구현한다.
• 문제의 핵심은 어떻게 g-h or h-g를 지나치는지이다.
• 조금만 비상하게 생각하면 되는데 모든 간선의 d에 *2를 하고 g-h를 잇는 간선에만 -1를 취하여 홀수로 취급한다. 따라서 도착한 경로의 값이 양수면 g-h를 지나치지 않은 것이고, 도착한 경로의 값이 음수면 g-h를 지나친 것을 확인할 수 있다.

💻 코드

import sys
import heapq

def dijikstra(s, e, g, h):
    check = 0
    q = []
    dist = [1e9 for x in range(n+1)]
    dist[s] = 0
    heapq.heappush(q, (0,s))
    while q:
        d, now = heapq.heappop(q)
        if d > dist[now]: continue
        for nj, nd in graph[now]:
            cost = d + nd
            if cost < dist[nj]:
                dist[nj] = cost
                heapq.heappush(q, (cost, nj))

    return dist

tc = int(sys.stdin.readline())
while tc!=0:
    result = []
    n, m, t = map(int, sys.stdin.readline().split())
    s, g, h = map(int, sys.stdin.readline().split())
    graph = [[]for x in range(n+1)]
    for i in range(m):
        a, b, d = map(int, sys.stdin.readline().split())
        setdist = d*2
        if (a == g and b == h) or (a==h and b == g):
            setdist -=1
        graph[a].append((b, setdist))
        graph[b].append((a, setdist))
    tlist = []
    for i in range(t):
        x = int(sys.stdin.readline())
        tlist.append(x)
        dist = dijikstra(s,x,g,h)
        if dist[x] %2 == 1:
            result.append(x)
    result.sort()
    for r in result:
        print(r, end=" ")

    tc-=1

• 다익스트라는 다 구현해놓고 간선을 구별하는 아이디어가 떠오르지 않은 것이 아쉬웠다..힝

참고링크: https://pangtrue.tistory.com/255