특정 거리의 도시 찾기

💻 입력 조건

• 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어집니다. (2 <= N <= 300,000, 1 <= M <= 1,000,000, 1 <= K <= 300,000, 1 <= X <= N)
• 둘째 줄부터 m 개의 줄에 걸쳐서 두 개의 자연수 A, B가 주어지며, 각 자연수는 공백으로 구분합니다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미입니다. (1 <= A, B <= N) 단 A와 B는 서로 다른 자연수입니다.

💻 출력 조건

• X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력합니다.
• 이때 도달할 수 있는 도시 중에서 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력합니다.

💻 입력 예시1

4 4 2 1
1 2
1 3
2 3
2 4

💻 출력 예시1

4

💻 입력 예시2

4 3 2 1 
1 2
1 3
1 4

💻 출력 예시2

-1

💻 입력 예시3

4 4 1 1
1 2
1 3
2 3
2 4

💻 출력 예시3

2
3

📖 문제 해결
bfs를 이용하여 출발 도시와 연결되어 있는 도시들과의 최단 거리를 모두 계산하고 특정 거리에 있는 도시를 찾고자 하였습니다. 구체적으로 설명하자면 다음과 같습니다. 우선, deque() 함수를 이용하여 현재 도시와 연결되어 있는 도시를 queue에 넣어 놓고, 넣었던 순서대로 빼서 또다시 연결되어 있는 도시를 찾아 queue에 넣어 가며 거리를 계산해나갔습니다. 이때 최단 거리를 계산하기 위함이므로 이미 계산한 이력이 있다면 (즉, distance[city_num] != 0인 경우) 큐에 다시 넣지 않도록 하였습니다. queue에 남은 도시가 없다면 계산을 멈추고 알고리즘을 통해 업데이트된 distance list 내에 특정 거리의 값을 가지고 있는 도시의 index를 출력하고, 없다면 -1을 출력하도록 하였습니다.

# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시의 번호 입력받기
n, m, k, x = list(map(int,input().split()))

# 도로 정보 입력받기
road = []
for i in range(m):
    road.append(list(map(int,input().split())))
    
# distance는 출발 도시로부터의 최단 거리 기록을 위한 list
distance = [0]*(n+1)

from collections import deque

queue = deque()

# 출발 도시를 queue에 추가
queue.append(x)

# count는 최단 거리 계산을 위한 변수
count = 0

# 출발 도시와 직접적으로 혹은 간접적으로 연결되어 있는 모든 도시들에 대한 최단 거리를 계산
while queue:
    
    i = queue.popleft()
    count += 1
    
    # 매 iteration마다 도로 정보를 모두 확인하며 최단 거리를 계산해 나감
    for r_inform in road:
        
        # '최단 거리'를 계산하기 위해 distance[city_num]==0인 경우만 계산
        if r_inform[0] == i and distance[r_inform[1]] == 0:
            
            now = r_inform[1]
            queue.append(r_inform[1])
            distance[now] = count
            
        elif r_inform[1] == i and distance[r_inform[0]] == 0:
            
            now = r_inform[0]
            queue.append(r_inform[0])
            distance[now] = count
            
# 출발 도시에서 출발 도시의 거리는 0 (알고리즘 상 2가 되어있을 경우도 있으므로 수정 필요)
distance[x] = 0

# distance list 내에서 특정 거리에 있는 도시를 찾아 출력 
for idx, dis in enumerate(distance):
    if dis == k:
        print(idx)
        
# 특정 거리에 있는 도시가 없다면 
if distance.count(k) == 0:
    print(-1)