작성자: 조광형
작성일: 2024년 11월 26일
문제 정의
주어진 도시와 거리 정보를 바탕으로, 특정 거리 K에 정확히 도달할 수 있는 도시 목록을 구하는 문제입니다.
각 도시는 번호로 표현되며, 두 도시 간의 거리 정보는 양방향 도로로 연결된 형태로 주어집니다.
목표는 K만큼 떨어진 도시를 찾는 것입니다.
예를 들어, N개의 도시가 있고, M개의 도로가 있으며, 출발 도시가 주어질 때 K만큼 떨어진 도시를 출력합니다.
입력
- N: 도시의 개수 (1 ≤ N ≤ 300,000)
- M: 도로의 개수 (1 ≤ M ≤ 1,000,000)
- K: 거리 정보 (0 ≤ K ≤ 300,000)
- X: 출발 도시 번호 (1 ≤ X ≤ N)
- 도로 정보: A, B (A에서 B로 가는 도로)
출력
특정 거리 K에 있는 도시의 번호를 오름차순으로 출력하고, 그러한 도시가 없으면 -1을 출력합니다.
예제
입력:
4 4 2 1
1 2
1 3
2 3
2 4
출력:
4
설명: 도시 1에서 시작할 때, 거리 2에 있는 도시 4가 유일합니다.
알고리즘 접근 방법
이 문제는 그래프 탐색 알고리즘을 활용하여 해결할 수 있습니다.
도시들을 노드로, 도로를 간선으로 표현한 그래프를 구성합니다.
BFS(너비 우선 탐색) 알고리즘을 이용하여 시작 도시 X에서부터 거리 K에 도달하는 도시를 찾는 방식으로 접근합니다.
BFS는 최단 경로를 찾는 데 유용하며, 대규모 그래프에서도 효율적으로 동작하기 때문에 이 문제에 적합합니다.
문제 해결 과정
1. 그래프 생성
먼저, 도로 정보로부터 그래프를 생성합니다.
리스트를 이용하여 그래프를 표현하고, 각 도시를 키로 사용하여 연결된 도시를 값으로 가지는 딕셔너리를 사용합니다.
2. BFS 구현
BFS를 구현하기 위해 큐를 사용합니다.
시작 도시를 큐에 추가하고, 방문한 도시를 기록합니다.
각 도시에 대해 방문할 거리 K인 도시를 탐색합니다.
3. 출력 처리
BFS 탐색 후, K거리 도시에 해당하는 도시 번호를 정렬하여 출력하거나, 도시가 없는 경우 -1을 출력합니다.
Python 코드
from collections import deque
def find_cities_with_distance(n, m, k, x, roads):
# 그래프 생성
graph = [[] for _ in range(n + 1)]
for a, b in roads:
graph[a].append(b)
# BFS 초기화
distance = [-1] * (n + 1)
distance[x] = 0
queue = deque([x])
while queue:
city = queue.popleft()
for neighbor in graph[city]:
if distance[neighbor] == -1: # 방문하지 않은 도시
distance[neighbor] = distance[city] + 1
queue.append(neighbor)
# 결과 생성
result = [i for i in range(1, n + 1) if distance[i] == k]
return result if result else [-1]
# Test case
n = 4
m = 4
k = 2
x = 1
roads = [(1, 2), (1, 3), (2, 3), (2, 4)]
print(find_cities_with_distance(n, m, k, x, roads))
이 코드는 BFS를 사용하여 특정 거리 K에 도달할 수 있는 도시를 찾습니다. 그래프는 인접 리스트로 표현되며 간선 정보를 바탕으로 노드 간의 연결 관계를 정의합니다.
결론
“특정 거리의 도시 찾기” 문제는 그래프 탐색 알고리즘, 특히 BFS를 통해 효율적으로 해결할 수 있는 문제입니다.
이 문제를 통해 BFS의 기본 원리, 그래프를 구성하는 방법, 그리고 최단 거리 탐색에 대한 이해를 높일 수 있습니다.
기초부터 시작하여, 더 복잡한 그래프 문제로 나아갈 수 있는 디딤돌이 될 것입니다.