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

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

Question

Language: Python

Difficulty: Silver 2

전형적인 dfs/bfs 문제로 시작 정점으로 부터 bfs, dfs를 수행하면서 distance 배열에 각각의 정점까지의 거리를 저장하였다.

이후, distance 배열을 참조하여 특정 거리 k를 만족하는 정점을 출력하도록 하고, 거리가 k인 정점이 없는 경우는 -1를 출력하도록 한다.

Solution

from collections import deque

v,e,k,start_node=map(int,input().split())
graph=[[] for _ in range(v+1)]
for _ in range(e):
    v1,v2=map(int,input().split())
    graph[v1].append(v2)
distance=[-1] * (v+1)
queue=deque()

distance[start_node]=0
queue.append(start_node)

while queue:
    vertex=queue.popleft()
    for adj_vertex in graph[vertex]:
      if distance[adj_vertex]==-1:
        distance[adj_vertex]=distance[vertex]+1
        queue.append(adj_vertex)
        
count=0
for i in range(1,v+1):
  if distance[i] == k:
    count+=1
    print(i)
    
if count==0:
    print(-1)