[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 13 DFS/BFS 문제 - Q15 특정 거리의 도시 찾기

1) 문제

 

 

2) 코드

from collections import deque

# 정보 받기
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]


# 도로 정보 받기
# 각 지점에서 연결 된 곳 정보 받기
for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)


# 모든 도시 최단 거리 초기화
distance = [False] * (n+1)

# 출발 도시까지의 거리는 0으로 설정
distance[x] = 0


# bfs 수행
q = deque([x])
while q:
  # q의 맨 왼쪽 값 now에 넣기
  now = q.popleft()
  # 현재 도시에서 이동할 수 있는 모든 도시를 확인
  for next_node in graph[now]:
    # 아직 방문하지 않은 도시라면
    if distance[next_node] == False:
      # 최단 거리 갱신
      distance[next_node] = distance[now] + 1
      q.append(next_node)

# 최단 거리가 k인 모든 도시의 번호를 오름차순으로 출력
check = False
for i in range(1, n+1):
  if distance[i] == k:
    print(i)
    check = True

# 만약 최단 거리가 k 인 도시가 없다면, -1 출력
if check == False:
  print(-1)