안녕하세요! 오늘은 코틀린을 이용한 코딩테스트 문제를 하나 풀어보려고 합니다. 주제는 “연결 요소의 개수 구하기”입니다. 이 문제는 그래프 이론과 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)의 이해를 요구합니다. 이 문제를 통해 그래프와 연결 요소에 대한 개념을 확장해보겠습니다.
문제 설명
주어진 정점의 개수 N과 간선의 개수 M이 있을 때, N개의 정점을 가진 무향 그래프가 주어집니다. 이 그래프에서 연결 요소의 개수를 구하는 프로그램을 작성하세요. 연결 요소란, 서로 연결된 정점들의 집합을 말합니다.
입력
- 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1000)와 간선의 개수 M (0 ≤ M ≤ 10000)이 주어진다.
- 다음 M줄에는 간선의 정보가 주어진다. (정점 A, 정점 B, 1 ≤ A, B ≤ N)
출력
- 연결 요소의 개수를 출력한다.
예제 입력
6 5
1 2
2 5
5 1
3 4
6 2예제 출력
2문제 풀이 과정
이 문제를 해결하기 위해서 우리는 DFS(혹은 BFS)를 이용하여 그래프의 모든 연결 요소를 탐색할 수 있습니다. 이렇게 하면 각 연결 요소를 한 번씩 방문하면서 그 카운트를 증가시킬 수 있습니다. 전체 과정은 다음과 같습니다.
1. 그래프 표현
먼저, 그래프를 인접 리스트를 사용하여 표현합니다. 인접 리스트는 각 정점에 연결된 정점의 리스트를 유지하는 방식입니다. 이를 위해 빈 리스트를 만들고 각 정점에 대해 연결된 정점을 추가합니다. 코틀린에서는 MutableList를 사용할 수 있습니다.
2. DFS 함수 구현
DFS를 이용하여 그래프를 탐색하는 함수를 구현합니다. 이 함수는 특정 정점을 방문하고 그 정점과 연결된 모든 정점을 재귀적으로 방문합니다. 방문한 정점은 추후에 중복 방문하지 않도록 표시합니다.
3. 연결 요소 Count
모든 정점에 대해서 DFS를 호출하여 연결 요소의 개수를 셉니다. 만약 DFS가 호출되면 그 카운트를 증가시킵니다.
코드 구현
이제 위의 과정을 코드로 구현해봅시다. 아래는 코틀린으로 작성한 코드입니다.
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val graph = MutableList(n + 1) { mutableListOf() }
for (i in 0 until m) {
val (a, b) = readLine()!!.split(" ").map { it.toInt() }
graph[a].add(b)
graph[b].add(a)
}
val visited = BooleanArray(n + 1)
var count = 0
fun dfs(vertex: Int) {
visited[vertex] = true
for (neighbor in graph[vertex]) {
if (!visited[neighbor]) {
dfs(neighbor)
}
}
}
for (i in 1..n) {
if (!visited[i]) {
dfs(i)
count++
}
}
println(count)
} 4. 시간 복잡도 분석
본 알고리즘의 시간 복잡도는 O(N + M)입니다. 여기서 N은 정점의 개수, M은 간선의 개수입니다. 따라서 그래프를 한번 방문하고 모든 간선을 탐색하는 데 걸리는 시간과 비례합니다.
결론
이번 강좌를 통해 연결 요소의 개수를 구하는 문제를 해결하는 방법을 익혔습니다. 그래프 이론 및 DFS/BFS의 기본을 잘 이해하고 활용하는 것은 코딩 테스트에 매우 중요합니다. 이 알고리즘의 기초를 잘 다져두면 다양한 문제를 해결하는 데 큰 도움이 될 것입니다.
이제 연습 문제를 통해 이론을 더욱 확실히 하고 코딩 테스트 준비에 힘쓰기를 바랍니다. 다음 강좌에서 또 만나요!