[백준] 9370번 : 미확인 도착지

9370번: 미확인 도착지

9370번: 미확인 도착지

🤔 문제분석

s에서 e로 갈때 g, h를 방문했는지 여부를 확인하는 문제로 데이크스트라를 s에서 시작, g에서 시작, h에서 시작하여 각각의 거리를 측정한뒤 아래의 조건을 만족하면 s 에서 e로 갈때 g, h를 방문했는지 확인 할 수 있다.

1. d_s[g] + d_g[h] + d_h[e] == d_s[e] 일때
2. d_s[h] + d_h[g] + d_g[e] == d_s[e] 일때

💻 코드

import sys
import heapq

input = sys.stdin.readline

def dijikstra(start):
    distance = [INF] * (n+1)
    distance[start] = 0
    queue = []
    heapq.heappush(queue, (0, start))
    while queue:
        cost, node = heapq.heappop(queue)
        
        if distance[node] < cost:
            continue
        
        distance[node] = cost
        
        for child, c in edge[node]:
            new_cost = c + cost
            if distance[child] > new_cost:
                distance[child] = new_cost
                heapq.heappush(queue, (new_cost, child))
    
    return distance

T = int(input())

for _ in range(T):
    n, m, t = map(int, input().split())
    INF = sys.maxsize
    s, g, h = map(int, input().split())
    edge = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, d = map(int, input().split())
        edge[a].append((b, d))
        edge[b].append((a, d))
        
    d_s = dijikstra(s)
    d_h = dijikstra(h)
    d_g = dijikstra(g)
    
    result = []
    for _ in range(t):
        e = int(input())
        if (d_s[h] + d_h[g] + d_g[e] == d_s[e]) or (d_s[g] + d_g[h] + d_h[e] == d_s[e]):
            result.append(e)
    
    print(*sorted(result))

🎯 피드백 및 개선사항

처음에는 한번의 데이크스트라를 한뒤에 역추적 하는 방식으로 문제를 접근하였습니다. 역추적 하는 방식에서 너비우선탐색을 사용하여 추적하게 되는데 여기서 시간 + 메모리 오류 판정을 받았습니다.

데이크 스트라를 각각의 위치에서 반복하여 조건을 만족하는 경우의 수를 구하는 방법을 오늘 또 하나 알아갑니다.