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

 

📌문제 탐색하기

• 어떤 나라에 1번부터 N(2 ≤ N ≤ 300,000)번까지의 도시와 M(1 ≤ M ≤ 1,000,000)개의 단방향 도로가 존재
  • 모든 도로의 거리는 1
• 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K(1 ≤ K ≤ 300,000)인 모든 도시들의 번호를 출력하기
  • 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 0이라고 가정

이 문제에서는 각 도시를 정점, 각 도시와 연결된 단방향 도로를 간선으로 생각하면 나라의 도로 정보를 그래프로 표현할 수 있다. 즉, 출발 도시 X에서 그래프 탐색을 통해 연결된 다른 도시까지의 거리를 구할 수 있고, 그 중 최단 거리가 정확히 K인 도시인 경우를 찾아낼 수 있다.

X에서 다른 도시들까지 너비 우선 탐색(BFS)을 수행하는 경우 시간복잡도는 O(N+M)으로 시간 내에 풀이가 가능하다.

 

---

📌코드 설계하기

1. 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X 입력 받기
2. 단방향 도로 정보를 저장할 인접리스트 roads 생성하기
3. M개의 도로 정보(출발지 A, 도착지 B)를 입력받아 roads 갱신하기
4. X부터 각 도시까지의 최단 거리를 기록할 리스트 distances 생성하기
5. X부터 시작해서 BFS 탐색 수행하며 distances 갱신하기 (방문여부는 distances 요소로 판별)
   
   1. 현재 거리가 이미 K인 도시 이후부터는 탐색을 하지 않기 위해 큐에 추가하지 않는다.
6. distances가 K인 도시들을 오름차순으로 출력하기

 

---

📌정답 코드

from collections import deque
import sys

input = sys.stdin.readline

N, M, K, X = map(int, input().split())
roads = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(lambda x: int(x)-1, input().split())
    roads[A].append(B)

distances = [-1]*N

q = deque([X-1])
distances[X-1] = 0
has_city_at_K = False

while q:
    cur_city = q.popleft()
    for next_city in roads[cur_city]:
        if distances[next_city] == -1:
            distances[next_city] = distances[cur_city] + 1
            if distances[next_city] < K:
                q.append(next_city)
            if distances[next_city] == K:
                has_city_at_K = True

if has_city_at_K:
    for i in range(N):
        if distances[i] == K:
            print(i+1)
else:
    print(-1)