[이것이 코딩테스트다] 특정 거리의 도시 찾기

🗃️문제 설명

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

🖥️코드

import sys
input = sys.stdin.readline
from collections import deque

N, M, K, X = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [-1] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)

def BFS(x):
    q = deque()
    q.append(x)
    visited[x] = 0
    while q:
        t = q.popleft()
        for i in graph[t]:
            if visited[i] == -1:
                visited[i] = visited[t] + 1
                q.append(i)

BFS(X)

result = []
for idx, v in enumerate(visited):
    if v == K:
        result.append(idx)

if len(result) > 0:
    result.sort()
    for i in result:
        print(i)
else:
    print(-1)

🧠아이디어

알고리즘 유형 : DFS/BFS

최단 거리 배열을 만들고 이동 시마다 증가 처리를 시켜주고 X에서 출발하여 최단 거리가 K를 만족하는 노드를 차례대로 출력

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 특정 거리의 도시 찾기
모범 답안 - 특정 거리의 도시 찾기