[BOJ] 특정 거리의 도시 찾기

---

코드

import sys
import heapq
input = sys.stdin.readline

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
dist = [10e9]*(n+1)

ans = sys.maxsize

for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)

def dijkstra(start):
    # 최소 힙 다익스트라 (O(ElogV))
    q = []
    heapq.heappush(q, (0, start))    # (인접노드까지의 최소비용, 인접노드)
    dist[start] = 0

    while q:
        d, now = heapq.heappop(q)
        if dist[now] < d:
            continue
        for adj in graph[now]:
            cost = d + 1
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))

dijkstra(x)
if k not in dist:
    print(-1)
else:
    for i in range(n+1):
        if dist[i] == k:
            print(i)
            

결과

풀이 방법

• 다익스트라 또는 bfs로 해결할 수 있는 문제이다. 다익스트라 알고리즘 복습 겸 해당 알고리즘으로 풀이하였다.

---