백준 1012번: 유기농 배추 - 상세 풀이
🔍 1. 문제 소개
이 문제는 강원도 고랭지에서 유기농 배추를 재배하는 한나 씨의 이야기입니다. 해충으로부터 배추를 보호하기 위해 배추흰지렁이를 사용하는데, 인접한 배추는 하나의 지렁이로 충분히 보호할 수 있습니다. 배추밭의 크기와 배추의 위치 정보가 주어지면, 최소 몇 마리의 배추흰지렁이가 필요한지 구하는 문제입니다. 배추는 상하좌우로 인접한 배추와 연결되어 있다고 간주합니다.
💡 2. 문제 해석
문제의 핵심은 서로 연결된 배추들의 무리를 찾는 것입니다. 각 무리는 하나의 배추흰지렁이로 보호할 수 있으므로, 연결된 배추 무리의 개수를 세는 것이 문제 해결의 핵심입니다. 입력으로는 배추밭의 가로 길이(M), 세로 길이(N), 그리고 배추의 개수(K)와 각 배추의 좌표(X, Y)가 주어집니다. 제약 조건으로는 M, N, K의 크기가 제한되어 있습니다 (1 ≤ M, N ≤ 50, 1 ≤ K ≤ 2500).
🧠 3. 접근 방법
이 문제는 그래프 탐색 알고리즘을 사용하여 효율적으로 해결할 수 있습니다. 특히, 깊이 우선 탐색(Depth-First Search, DFS) 또는 **너비 우선 탐색(Breadth-First Search, BFS)** 알고리즘을 사용하면 연결된 배추들을 효과적으로 찾을 수 있습니다.
알고리즘은 다음과 같습니다:
- 배추밭을 나타내는 2차원 배열을 생성합니다.
2. 입력으로 주어진 배추의 위치를 배열에 표시합니다. 3. 배열을 순회하며 방문하지 않은 배추를 만나면 DFS(또는 BFS)를 사용하여 연결된 모든 배추를 방문 표시합니다. 방문 표시된 배추들은 하나의 무리에 속합니다. 4. 하나의 무리를 방문할 때마다 카운터를 증가시킵니다. 5. 최종적으로 카운터의 값이 최소 필요한 배추흰지렁이의 수가 됩니다.
⚙️ 4. 구현 과정
- 배추밭을 나타내는 `BooleanArray`의 배열인 `cabbageFields`를 생성합니다. `true`는 배추가 심어져 있음을, `false`는 배추가 없음을 의미합니다.
2. 입력으로 주어진 배추의 위치를 `cabbageFields`에 저장합니다. 3. `visited` 배열을 생성하여 이미 방문한 배추를 추적합니다. 4. 이중 for 문을 사용하여 `cabbageFields`를 순회합니다. 5. 만약 현재 위치에 배추가 있고 아직 방문하지 않았다면, DFS 함수를 호출하여 연결된 모든 배추를 방문 표시하고 카운터를 증가시킵니다. 6. 최종적으로 카운터의 값을 출력합니다.
💻 5. 코드 설명
fun main() {
val t = readLine()!!.toInt()
repeat(t) {
val (m, n, k) = readLine()!!.split(" ").map { it.toInt() }
val cabbageFields = Array(n) { BooleanArray(m) }
repeat(k) {
val (x, y) = readLine()!!.split(" ").map { it.toInt() }
cabbageFields[y][x] = true
}
var count = 0
val visited = Array(n) { BooleanArray(m) }
for (i in 0 until n) {
for (j in 0 until m) {
if (cabbageFields[i][j] && !visited[i][j]) {
dfs(cabbageFields, visited, i, j)
count++
}
}
}
println(count)
}
}
fun dfs(cabbageFields: Array, visited: Array, row: Int, col: Int) {
if (row !in 0 until cabbageFields.size || col !in 0 until cabbageFields[0].size ||
!cabbageFields[row][col] || visited[row][col]) {
return
}
visited[row][col] = true
dfs(cabbageFields, visited, row + 1, col)
dfs(cabbageFields, visited, row - 1, col)
dfs(cabbageFields, visited, row, col + 1)
dfs(cabbageFields, visited, row, col - 1)
}
main 함수는 입력을 받고 DFS를 호출하여 연결된 배추 무리를 찾습니다. dfs 함수는 깊이 우선 탐색을 구현하여 연결된 모든 배추를 방문 표시합니다. visited 배열은 이미 방문한 배추를 추적하여 무한 루프를 방지합니다.
⏱️ 6. 시간 복잡도와 공간 복잡도 분석
* 시간 복잡도: 최악의 경우 모든 배추가 연결되어 있을 때, DFS는 모든 배추를 한 번씩 방문하게 됩니다. 따라서 시간 복잡도는 O(N*M)입니다. M과 N은 각각 배추밭의 가로, 세로 길이입니다.
* 공간 복잡도: cabbageFields와 visited 배열은 모두 N*M의 크기를 가지므로, 공간 복잡도는 O(N*M)입니다.
🎯 7. 결론
이 문제는 DFS(또는 BFS)를 이용한 그래프 탐색 알고리즘을 통해 효율적으로 해결할 수 있습니다. 주어진 제약 조건 내에서 시간 및 공간 복잡도 모두 충분히 효율적입니다. 코드의 가독성을 높이고 효율성을 조금 더 높이기 위해 Kotlin의 range operator와 implicit initialization을 활용했습니다. 이 문제를 통해 그래프 탐색 알고리즘의 이해와 구현 능력을 향상시킬 수 있었습니다. 추가적인 개선으로는, 더욱 효율적인 그래프 표현 방법을 고려할 수 있지만, 현재 문제의 입력 크기에서는 큰 성능 향상을 기대하기 어렵습니다.