[백준/알고리즘] #18352: 특정 거리의 도시 찾기 [파이썬(python)/DFS/BFS]

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

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

첫 번호를 지정하는 문제는 처음이라 deque() 선언하고 append로 X를 넣었었는데 채점하다가 60%쯤에서 자꾸 틀렸습니다 로 떴다. 다른 풀이들 참고해서 처음 큐 선언부터 deque([X])로 해주니 해결되었다.

 

visited를 다 0으로 채워서 선언하는 게 익숙했었는데, visited에 카운트하는 경우에는 아예 init을 -1로 해야겠다 느꼈다. 첫 출발 번호만 0으로 바꾸고 탐색을 시작해야지 실수로 결과값에 0이 안 뽑혀나온다. 

 

파이썬 코드

#18352_특정거리의 도시 찾기
import sys
from collections import deque
input = sys.stdin.readline

N, M, K, X = map(int,input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = list(map(int,input().split()))
    graph[a].append(b) #단방향 

visited = [-1]*(N+1) 
q = deque([X])
visited[X]=0

while q: #bfs search
    cur = q.popleft()
    for i in graph[cur]:
        if visited[i]==-1:
            visited[i] = visited[cur]+1
            q.append(i)
      
flag = 0
for i in range(N+1):
    if visited[i]==K:
        print(i)
        flag = 1
        
if flag==0:
    print("-1")