(BFS)백준 18352 특정 거리의 도시 찾기 - python

 

BFS -> 특정 거리의 도시 찾기

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

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

--popleft() 함수를 사용하는 이유

*list의 pop() 마지막 값 꺼낼 때=> O(1) (일정한 시간) 

          pop(0) 처음 값 꺼낼 때 => O(n) (list에 따라 다른 시간)

 

*deque 사용 시 popleft() = list의 pop(0) => O(1)이 걸린다.

 

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)
    
# 거리 초기화
# 자기자신 거리 0
distance = [-1] * (n+1)
distance[x] = 0

# 출발지 x 삽입
q = deque([x])

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

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