[알고리즘|파이썬] 백준 18352 특정 거리의 도시 찾기

문제 링크: https://www.acmicpc.net/problem/18352

 

📌 문제 탐색하기

시간 제한: 2초
메모리 제한: 256 MB

 

 

✏️ 구해야 하는 정답

주어진 그래프에서 특정 도시 X에서 출발하여 최단 거리 K에 있는 모든 도시의 번호를 찾아야 한다.

모든 도로의 거리가 1이므로, BFS (너비 우선 탐색) 를 사용하면 최단 거리를 효율적으로 구할 수 있다.

 

조건

- 2 ≤ N ≤ 300,000

- 1 ≤ M ≤ 1,000,000

- 1 ≤ K ≤ 300,000

- 1 ≤ X ≤ N

- 1 ≤ A, B ≤ N

- 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력

---

📌 풀이하기 

1️⃣ 그래프를 인접 리스트 형태로 표현

 

주어진 M개의 도로 정보를 통해 단방향 그래프를 구성한다.

graph[A] 리스트에 A에서 출발하는 도시들을 저장하여 인접 리스트를 만든다.

 

2️⃣ BFS 탐색을 사용하여 최단 거리 계산

 

• queue를 사용하여 출발 도시 X에서 시작

• 방문한 도시는 거리 정보를 리스트(dist)에 저장

• 모든 도로의 거리가 1이므로 현재 도시의 거리 + 1로 다음 도시의 거리를 설정

• 목표 거리 K에 도달한 도시들을 저장 후 오름차순 출력

 

3️⃣ K 거리의 도시가 없으면 -1 출력

 

BFS 탐색 후, 거리가 정확히 K인 도시가 없다면 -1을 출력해야 한다.

 

도시 번호: [ 1  2  3  4 ]
최단 거리: [ 0  1  1  2 ]

정답: 4

🚀 시간 복잡도 분석

• 그래프 저장: O(M)

• BFS 탐색: O(N + M)

• 결과 찾기: O(N)

 

---

📌 코드 설계하기

1. 입력 받기 (도시 개수 N, 도로 개수 M, 목표 거리 K, 출발 도시 X)

2. 인접 리스트 그래프 구성

3. BFS 탐색으로 최단 거리 리스트(dist) 업데이트

4. 최단 거리가 K인 도시를 찾고 출력 (없으면 -1 출력)

 

---

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.read
data = input().split("\n")

N, M, K, X = map(int, data[0].split())

graph = [[] for _ in range(N + 1)]
for i in range(1, M + 1):
    if data[i]:
        A, B = map(int, data[i].split())
        graph[A].append(B)

queue = deque([X])
dist = [-1] * (N + 1)
dist[X] = 0 

while queue:
    now = queue.popleft()
    for next_city in graph[now]:
        if dist[next_city] == -1:
            dist[next_city] = dist[now] + 1
            queue.append(next_city)

result = [i for i in range(1, N + 1) if dist[i] == K]
if result:
    print("\n".join(map(str, result)))
else:
    print(-1)