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

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

문제

어떤 나라에 1번부터 n번까지의 도시와 M개의 단방향 도로가 존재한다.

모든 도로의 거리는 1이다.

이 때 특정한 도시 X로 부터 출발해 도달할 수 있는 모든 도시 중 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오.

또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라 가정한다.

입력

• 첫 번째 줄: 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
• 두 번째 줄 ~: 두 개의 자연수 A, B

출력

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력

해결 방식

bfs 알고리즘

• visited 배열을 통해 이미 조사한 노드는 다시 조사하지 않도록 함
• distacne 배열에 통해 기준 노드로 부터의 거리 저장

예시

[[], [2, 3], [3, 4], [], []]

• 기준 노드: 1,
• k = 2
• queue = [1]

1. pop - data: 1
   • 노드 1가 연결되어 있는 노드: 2, 3
   • 노드 2와 3의 visted 배열의 데이터를 True로 변경
   • distance[2] = 1, distance[3] = 1
   • queue = [2, 3]
2. pop - data: 2
   • 노드 1가 연결되어 있는 노드: 3, 4
   • 노드 3와 4의 visted 배열의 데이터를 True로 변경
   • 노드 3의 visited 배열의 데이터가 이미 True 였으므로 pass
   • distance[4] = distance[2] + 1 = 1 + 1 = 2
   • queue = [3, 4]
3. queue 배열에 데이터가 없어질 때까지 과정 반복
4. distance 배열의 데이터가 2인 도시 출력

∴ 4

코드

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

# bfs 알고리즘
def bfs(x):
    queue = deque()
    queue.append(x)
    visited[x] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if visited[i] == False: # 방문하지 않은 노드의 경우
                queue.append(i)
                distance[i] = distance[v] + 1   # 거리 측정
                visited[i] = True   # 방문 표시
    
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]

visited = [False] * (n+1)
distance = [0] * (n+1)
result = []

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

bfs(x)

# 기준 노드로 부터의 거리가 k인 도시 저장
for i in range(n+1):
    if distance[i] == k:
        result.append(i)

# 출력
if len(result) != 0:
    print(*result, sep="\n")
else:
    print(-1)