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

이번에 해결해 볼 문제는 백준에 있는 특정 거리의 도시 찾기이다.

---

문제 설명

• 1 ~ N번까지의 도시와 M개의 단방향 도로가 존재
• 모든 도로의 거리는 1이다.
• 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시의 번호를 출력
• 출발 도시 X에서 X로 가는 최단 거리는 항상 0이다.

문제 아이디어

• 우선 그래프가 그려져 있으므로 그래프 문제로 생각한다.
• 연결 정보를 도시의 개수를 감안하여 인접 리스트(Adjacency List)로 초기화한다.
  • 인접 행렬(Adjacency Matrix)로 구현할 경우 행렬의 크기는 300,000 x 300,000이 되므로 매우 커진다.
• 연결된 도시 간의 거리는 1이므로 도시 X로부터 거리를 BFS를 통해 구할 수 있을 것이다.

문제 해결 코드

import sys
input = sys.stdin.readline

n, m, k, x = map(int, input().split())
city = [[i] for i in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    city[a].append(b)

# 도시 X로부터 최단 거리가 K인 도시 번호를 담은 리스트
result = []
# 해당 도시를 방문 했는지 여부 체크
visited = [False] * (n+1)

from collections import deque
def bfs(x):
    # q 저장 형태 : [도시, 도시까지 최단 거리]
    q = deque([[x,0]])
    visited[x] = True
    while q:
        c, dist = q.popleft()
        if dist == k:
            result.append(c)
        for i in city[c]:
            if not visited[i]:
                # 연결된 도시 간의 거리가 1이므로 최단 거리를 1씩 더해간다.
                q.append([i, dist+1])
                visited[i] = True

bfs(x)

if result:
    for i in sorted(result): print(i)
else:
    print(-1)

간단한 예시