백준 18352 : 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

 

해결 방법 : 다익스트라

• X를 출발점으로 모든 노드 최단거리 계산
• 사실 모든 노드 사이의 거리가 1이기 때문에 bfs로도 간단하게 풀릴 것 같은데 오랫만에 다익스트라 복습겸 사용해봤다.
  • 우선순위큐를 사용하기 때문에 cur_fee가 K보다 커지면 탐색 종료.

 

import sys
input = sys.stdin.readline
import heapq
from collections import defaultdict

def solution(N, M, K, X, loads):
    graph = defaultdict(list)
    fee = [float('inf')] * (N+1)
    fee[X] = 0

    for f, t in loads:
        graph[f].append(t)

    Q = [(fee[X], X)]

    while Q:
        cur_fee, cur_n = heapq.heappop(Q)
        if cur_fee > K: break
        if fee[cur_n] < cur_fee: continue

        for next_n in graph[cur_n]:
            if cur_fee + 1 < fee[next_n]:
                fee[next_n] = cur_fee + 1
                heapq.heappush(Q, (cur_fee + 1, next_n))

    answer = [str(i) for i in range(N+1) if fee[i] == K]

    return '\n'.join(answer) if len(answer) > 0 else -1

if __name__ == '__main__':
    N, M, K, X = map(int, input().split())
    loads = [tuple(map(int, input().split())) for i in range(M)]
    result = solution(N, M, K, X, loads)
    print(result)