작성일:
소개
안녕하세요, 이번 코틀린 코딩테스트 강좌에서는 ‘특정 거리의 도시 찾기’라는 알고리즘 문제를 다룹니다.
이 문제는 그래프 탐색 문제로, 주어진 조건에 따라 특정 거리의 도시에 있는 노드들을 찾는 알고리즘적 접근을 요구합니다.
코틀린을 사용하여 문제를 해결하는 방법을 단계별로 살펴보겠습니다.
문제 설명
주어진 그래프는 N개의 도시와 M개의 양방향 도로로 구성되어 있습니다.
각 도시는 1부터 N까지의 번호로 식별되며, 도로는 두 도시 사이에 연결되어 있습니다.
문제를 통해 주어진 거리 K를 갖는 모든 도시를 찾는 것이 목표입니다.
입력 형식
첫 번째 줄에는 도시의 개수 N (1 ≤ N ≤ 30000)과 도로의 개수 M (1 ≤ M ≤ 200000), 찾고자 하는 거리 K (0 ≤ K ≤ 30000)가 주어집니다.
두 번째 줄부터 M개의 줄에는 각각 연결된 두 도시 A, B (1 ≤ A, B ≤ N)의 정보가 주어집니다.
출력 형식
거리 K에 정확히 해당하는 도시의 번호를 오름차순으로 출력하되, 만약 그런 도시가 없다면 -1을 출력합니다.
문제 해결 접근법
이 문제는 그래프에서 주어진 조건에 맞는 정점을 탐색하는 문제입니다.
BFS(너비 우선 탐색) 알고리즘을 사용하여 적절한 깊이까지 탐색함으로써 특정 거리의 도시를 찾을 수 있습니다.
BFS는 비어 있는 큐와 인접 리스트를 이용하여 구현할 수 있습니다.
구현 방법
먼저 주어진 도시와 도로 정보를 기반으로 인접 리스트를 구성합니다.
그 후 BFS 알고리즘을 사용하여 주어진 거리 K에 도달하는 도시를 찾습니다.
구현 순서는 다음과 같습니다:
- 입력 값 처리: 도시의 개수, 도로의 개수, 거리 K를 읽어옵니다.
- 인접 리스트 구성: 각 도시와 연결된 다른 도시를 리스트 형태로 저장합니다.
- BFS 초기화: 시작 도시에서부터 K의 거리를 탐색합니다.
- 결과 저장: K 거리에 도달한 도시 번호를 리스트에 저장합니다.
- 결과 출력: K 시점에서 도달한 도시들을 정렬하여 출력합니다.
코드 구현
아래는 코틀린으로 구현한 BFS 알고리즘을 통한 해결 코드입니다:
import java.util.*
fun main() {
val scanner = Scanner(System.`in`)
val n = scanner.nextInt() // 도시의 개수
val m = scanner.nextInt() // 도로의 개수
val k = scanner.nextInt() // 찾고자 하는 거리
val x = scanner.nextInt() // 출발 도시
// 인접 리스트 초기화
val graph = Array(n + 1) { mutableListOf() }
// 도로 정보 입력 받기
for (i in 0 until m) {
val a = scanner.nextInt()
val b = scanner.nextInt()
graph[a].add(b)
graph[b].add(a)
}
// BFS 구현
val distance = IntArray(n + 1) { -1 }
distance[x] = 0
val queue: Queue = LinkedList()
queue.add(x)
while (queue.isNotEmpty()) {
val current = queue.poll()
for (neighbor in graph[current]) {
if (distance[neighbor] == -1) {
distance[neighbor] = distance[current] + 1
queue.add(neighbor)
}
}
}
// 결과 도시 찾기
val result = mutableListOf()
for (i in 1..n) {
if (distance[i] == k) {
result.add(i)
}
}
// 결과 출력
if (result.isEmpty()) {
println(-1)
} else {
result.sort()
for (city in result) {
println(city)
}
}
}
해설
위의 코드는 주어진 문제를 해결하기 위한 전형적인 BFS 구현 방식입니다.
특히 도로의 연결 상태를 인접 리스트로 표현하여 메모리 사용을 최적화하고, 빠른 탐색을 가능하게 합니다.
BFS는 모든 노드를 탐색하며, 노드와 연결된 인접 노드를 큐에 넣는 방식으로 작동합니다.
이렇게 하여 각 노드까지의 거리를 갱신하며 최종적으로 거리 K에서 멈춘 노드들을 수집합니다.
만약 거리가 K인 도시가 없을 경우, -1을 출력하며 결과를 처리하는 것도 좋은 프로그래밍 습관입니다.
이 코드 구조는 문제 유형에 맞춰 쉽게 수정할 수 있어 다양한 그래프 탐색 문제에 적용 가능합니다.
결론
이상으로 ‘특정 거리의 도시 찾기’ 문제를 비롯해 BFS 알고리즘을 활용한 코틀린 코드 구현 과정에 대해 알아보았습니다.
이 문제는 그래프 문제의 기초를 이해하는 데 도움을 주며, 다양한 문제 유형에 대한 문제 해결 능력을 키울 수 있습니다.
업무나 개인 프로젝트에서 알고리즘을 효율적으로 적용하는 데에도 많은 도움을 줄 것입니다.
추후 더 다양한 알고리즘 문제들도 다룰 예정이니 많은 관심 부탁드립니다.