18352-특정거리의도시찾기

www.acmicpc.net/problem/18352

모든 곳마다 그 곳 까지의 거리가 필요하다.

BFS 를 수행하면서 노드마다 최단거리를 얻어 놓는다.

최단 거리가 k 인 곳을 출력하면 된다.

from collections import deque

n,m,k,x = map(int,input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)

distance = [-1 for _ in range(n+1)]

q = deque([x])
distance[x] = 0

while q:
    now = q.popleft()
    for i in graph[now]:
        if distance[i] == -1:
            distance[i] = distance[now] + 1
            q.append(i)

cnt = 0
for i in range(1,n+1):
    if distance[i] == k:
        print(i)
        cnt += 1

if not cnt:
    print(-1)

Last updated