[백준]18352- 특정거리의 도시 찾기

<문제>
https://www.acmicpc.net/problem/18352

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

<풀이>

• 시작위치를 queue에 삽입한다.
• distance배열(시작위치에서 각 노드까지의 거리를 저장하는 배열)을 선언한다.
• distance배열에서 시작위치에 해당하는 인덱스의 값을 0으로 설정한다.
• queue에서 원소를 추출한다음 각 인접노드를 queue에 삽입한다.
• distance배열에서 각 노드에 해당하는 인덱스의 값을 갱신한다.(이동거리+1)
• 위 4,5번과정을 queue가 빌때까지 반복한다.
• distance배열에서 특정거리에 해당하는 값을 원소로 갖는 인덱스를 출력한다.

<코드-파이썬>

from collections import deque
import sys
n,m,dist,start = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
distance = [-1]*(n+1)
for  _ in range(m):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
def bfs(n,k):
    answer = []
    queue = deque()
    queue.append(n)
    distance[n] = 0
    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if distance[i] == -1:
                queue.append(i)
                distance[i] = distance[now]+1
                if distance[i] == k:
                    answer.append(i)
    if len(answer == 0):
        print(-1)
    else:
        answer.sort()
        for i in answer:
            print(i,end='\n')
# Check = False
# for i in range(1,len(distance)):
#     if distance[i] == k:
#         print(i)
#         Check = True
# if Check == False:
#     print(-1)

bfs(start,dist)