18352

## 🔒 문제. ## 18352 특정 거리의 도시 찾기
''' 입력 예시
## case 1.
N, M, K, X = 4, 4, 2, 1
road = [[],
        [2, 3],
        [3, 4],
        [],
        []
]

## case 2.
N, M, K, X = 4, 3, 2, 1
road = [[],
        [2, 3, 4],
        [],
        [],
        []
]

## case 3.
N, M, K, X = 4, 4, 1, 1
road = [[],
        [2, 3],
        [3, 4],
        [],
        []
]
'''
## case 1.
N, M, K, X = 4, 4, 2, 1
road = [[],
        [2, 3],
        [3, 4],
        [],
        []
]

#### 최단 거리 : bfs > deque 활용
from collections import deque

start = X  ## 초기값 세팅 : 시작 위치
to_do = deque()  ## 해야할 일 : 앞으로 더 갈 수 있는 도시
to_do.append(start)  ## 시작 위치에서부터 시작
distance = [float('inf')] * (N+1)  ## 거리값을 inf(무한대)로 초기화
distance[start] = 0 ## 시작 위치의 거리는 0으로 세팅

while to_do:
    now = to_do.popleft()  ## 해야할 일에서 현재 도시 추출
    for next_city in road[now]:  ## 현재 도시에서 연결된 여러 도시들에 대해 반복
        if distance[next_city] == float('inf'):  ## 연결된 도시 중 거리값이 무한대인 경우 (미방문)
            distance[next_city] = distance[now] + 1  ## 현재 도시에서까지의 거리 + 1
            to_do.append(next_city)  ## 연결된 도시의 연결된 도시들을 해야할 일에 추가

distance_result = [i for i, v in enumerate(distance) if v == K]  ## 최단거리가 K값과 정확히 일치하는 도시 추출

if distance_result == []:
    print(-1)  ## 최단거리가 K인 도시가 없는 경우 -1 리턴
else:
    while distance_result:
        print(distance_result.pop(0))