[BOJ-1012][백준 1012] 유기농 배추 [SILVER-2] [Solved by Kotlin]

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다.

이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1

입력 및 출력

• 입력: 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
• 출력: 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

풀이

재배지의 모든 점에서 인접해 있는 네 방향으로 다섯 번 이동하면서 배추가 심어진 영역의 수를 얻어낸다. 숫자판을 이동하기 위해 DFS(깊이우선 탐색) 알고리즘을 통해 탐색한다.
보통 그래프 탐색을 할 때에는 visited배열을 두어 탐색한 곳을 저장해두어 다음에는 탐색한 곳을 재탐색하지 않도록하는데, visited배열을 사용하지 않기 위하여 이미 탐색한 부분의 영역의 그래프의 값을 바꾸어 visit한 표시를 진행하였다.
이렇게 찾은 영역의 숫자를 출력한다.

코드

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*

val bw = BufferedWriter(OutputStreamWriter(System.out))
lateinit var graph: Array<IntArray>
fun main() = with(System.`in`.bufferedReader()) {
    // tc
    val n = readLine().toInt()
    for(i in 0 until n) {
        // 그래프 크기 및 배추의 개수 입력
        val (x, y, cabbage) = readLine().split(" ").map { it.toInt() }
        var cnt = 0
        // 그래프 초기화
        graph = Array(x) { IntArray(y) { 0 } }
        // 배추 위치 입력
        for (j in 0 until cabbage) {
            val (a, b) = readLine().split(" ").map { it.toInt() }
            graph[a][b] = 1
        }
        // 그래프 탐색
        for (a in 0 until x) {
            for (b in 0 until y) {
                if (dfs_1012(a, b)) {
                    cnt++
                }
            }
        }
        bw.write("$cnt\n")
    }

    bw.flush()
    bw.close()
    close()
}
fun dfs_1012(x: Int, y: Int): Boolean {
    if (x < 0 || x >= graph.size || y < 0 || y >= graph[0].size)
        return false
    if (graph[x][y] == 1) {
        graph[x][y] = 0
        dfs_1012(x, y - 1)
        dfs_1012(x, y + 1)
        dfs_1012(x - 1, y)
        dfs_1012(x + 1, y)
        return true
    }
    return false
}

DFS 알고리즘
DFS 알고리즘이란 그래프를 탐색할 때 한 방향으로 갈 수 있을 때 까지 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그곳으로부터 다시 다른 방향으로 갈 수 있을 떄까지 탐색을 반복하는 알고리즘이다.

본 문제에서는 다음과 같이 적용했다.

두 가지 조건을 통해 알고리즘이 수행된다.

1. 그래프 탐색 중 1을 만났을 때
2. 탐색 중 그래프 범위를 벗어났을 때

그래프 탐색 중 1을 만났을 때 에는 방문 처리를 위해 그 좌표의 값을 0으로 바꿔주었다.
보통 visited 배열을 따로 두어 방문 처리를 하지만, 이 문제에서는 탐색을 한 이후로 재방문 등 탐색 지점에 대한 별다른 작업을 추가적으로 하지 않기 때문에
그냥 값을 바꿔주는 것만으로도 방문처리를 해도 괜찮겠다고 생각하여 해당 방식으로 진행하였다.
또, visited 배열을 만들면 새로운 배열을 생성하는 것이므로 메모리도 조금 더 차지하게 되는데, 메모리적인 측면에서도 약간이나마 성능향상을 도모할 수 있었다.

해당 위치의 값을 0으로 바꿔 준 후, 재귀를 통해 탐색을 수행한다, 먼저 (x, y-1) 하단 방향으로 계속 탐색을 수행한다. 탐색을 계속 수행하다가 y값이 그래프를 벗어나게 되면
2번과정을 수행하고, 다음 재귀함수를 실행하여 다른방향으로 탐색을 진행한다.

이러한 방식으로 모든 점을 사방 탐색하면서 배추가 심어진 영역의 갯수를 더해 나아간다.

결과

제한 메모리와 제한시간과 비교해보면 괜찮을 결과를 보인다.