[BOJ] 18352번: 특정 거리의 도시 찾기 (파이썬)

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

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

---

출발 도시부터 시작하여 방문 가능한 도시들로 이동하며 필요한 거리를 갱신합니다.

• 방문하지 않은 도시에 대한 거리는 -1로 초기화합니다
• 출발 도시까지의 거리는 0으로 초기화합니다
• BFS
  • 현재 도시 cur 에서 방문할 수 있는 도시 vertices[cur] 들을 확인합니다
    • 아직 방문하지 않았다면(거리가 -1이라면)
      
      • "현재 도시까지의 거리 + 1"값을 해당 도시 dist[next] 에 대한 최단거리로 갱신합니다
      • 다음에 방문할 도시 목록에 추가합니다
• 최단거리가 k인 도시들을 오름차순으로 탐색하여 출력합니다
• 결과가 존재하지 않는다면 -1을 출력합니다

 

import sys
from collections import deque

n, m, k, x = map(int, sys.stdin.readline().rstrip().split())
edges = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(m)]

vertices = [[] for _ in range(n + 1)]
for e in edges:
    vertices[e[0]].append(e[1])

dist = [-1] * (n + 1)
dist[x] = 0
dq = deque([x])
while dq:
    cur = dq.popleft()
    for next in vertices[cur]:
        if dist[next] == -1:
            dist[next] = dist[cur] + 1
            dq.append(next)

result = [i + 1 for i in range(n) if dist[i + 1] == k]
if result:
    for r in result:
    	print(r)
else:
    print(-1)