[백준 실버2] 특정 거리의 도시 찾기 (#18352, 그래프 탐색 문제)

 

(문제 링크)

 

문제

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

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

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

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

 

입력 조건

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

 

출력 조건

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

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

 

입력 예시

4 4 1 1
1 2
1 3
2 3
2 4

 

출력 예시

2

3

 

---

문제 해결 흐름

1. 그래프 탐색 문제로 접근
   • 도시 간의 도로를 그래프의 노드와 간선으로 표현할 수 있다.
   • 각 도시를 노드로, 도로를 간선(거리1)으로 생각하면 문제는 최단 경로 탐색으로 해석할 수 있다.
2. 최단 거리 탐색에  BFS 이용
   • BFS는 모든 경로를 동일한 깊이로 탐색하기 때문에 최단 경로를 보장한다.
   • 출발 도시 X에서 BFS를 수행하여 각 도시까지의 최단 거리를 계산한다.
3. 탐색 방법
   • 출발 도시 X에서 BFS를 시작한다.
   • 현재 노드에서 이동할 수 있는 모든 인접 노드로 이동하며, 거리를 1씩 증가시킨다.
   • 탐색이 끝난 후, 최단 거리가 정확히 K인 도시들을 출력한다.

---

코드 설명

 

1. 입력 및 그래프 초기화

from collections import deque
import sys

# 빠른 입력을 위해 sys.stdin.readline 사용
input = sys.stdin.readline

# 도시, 도로, 거리, 출발 도시 입력
n, m, k, x = map(int, input().split())

# 그래프 초기화 (1번부터 N번 도시 사용)
graph = [[] for _ in range(n + 1)]

# 도로 정보 입력
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)

• graph는 각 도시에서 이동 가능한 다른 도시들을 리스트로 저장한다.
• 즉, graph[1] = [2,3]은 1번 도시에서 2,3번 도시로 이동할 수 있음을 의미 

 

2. BFS 함수 정의

def bfs(start):
    # 큐와 거리 배열 초기화
    queue = deque([start])
    distance = [-1] * (n + 1)  # 모든 도시는 초기값 -1 (미방문 상태)
    distance[start] = 0  # 출발 도시의 거리는 0

    # BFS 탐색 시작
    while queue:
        current = queue.popleft()

        # 현재 노드에서 인접 노드 탐색
        for next_node in graph[current]:
            # 아직 방문하지 않은 도시라면
            if distance[next_node] == -1:
                # 최단 거리 갱신 및 큐에 추가
                distance[next_node] = distance[current] + 1
                queue.append(next_node)

    # 결과 출력 처리
    result = [i for i in range(1, n + 1) if distance[i] == k]
    
    if result:
        for city in sorted(result):
            print(city)
    else:
        print(-1)

• distance 배열을 사용해 각 도시의 최단 거리를 저장한다. 초기값은 -1로 설정하여 방문 여부를 확인한다.
• BFS를 통해 출발 도시 X에서 모든 도시까지의 최단 거리를 계산한다. 

---

전체 코드

from collections import deque
import sys

# 빠른 입력을 위해 sys.stdin.readline 사용
input = sys.stdin.readline

# 도시, 도로, 거리, 출발 도시 입력
n, m, k, x = map(int, input().split())

# 그래프 초기화 (1번부터 N번 도시 사용)
graph = [[] for _ in range(n + 1)]

# 도로 정보 입력
for _ in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)

# BFS 함수 정의
def bfs(start):
    # 큐와 거리 배열 초기화
    queue = deque([start])
    distance = [-1] * (n + 1)  # 모든 도시는 초기값 -1 (미방문 상태)
    distance[start] = 0  # 출발 도시의 거리는 0

    # BFS 탐색 시작
    while queue:
        current = queue.popleft()

        # 현재 노드에서 인접 노드 탐색
        for next_node in graph[current]:
            # 아직 방문하지 않은 도시라면
            if distance[next_node] == -1:
                # 최단 거리 갱신 및 큐에 추가
                distance[next_node] = distance[current] + 1
                queue.append(next_node)

    # 결과 출력 처리
    result = [i for i in range(1, n + 1) if distance[i] == k]
    
    if result:
        for city in sorted(result):
            print(city)
    else:
        print(-1)

# BFS 수행
bfs(x)

 

• 각 도시를 최대 1번 방문하고, 모든 도로를 한 번씩 검사하므로 O(N+M)이다.