[13-01 DFS/BFS 문제] 특정 거리의 도시 찾기

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 에 있는 문제이다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

문제는 백준에 있다.

www.acmicpc.net/problem/18352

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

 

 

 

import sys
from collections import deque

input = sys.stdin.readline
INF = int(1e9)

n,m,k,x = map(int,input().split())
board = [[] for _ in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    board[a].append(b)

distance= [INF]*(n+1)
distance[x] = 0

q =deque()
q.append(x)
while q :
    now = q.popleft()
    for i in board[now]:
        if distance[i] == INF :
            distance[i] = distance[now]+1
            q.append(i)

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

if flag :
    print(-1)