백준 1012 유기농 배추

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

2차원 배열형태의 값이 주어지며 인접한 배열들을 재귀적으로 이동하며 문제를 해결해야 한다. 

 

import java.io.BufferedReader
import java.io.InputStreamReader

class FarmAndBug {

    private lateinit var farmArray: Array<Array<Boolean>>
    private var cabbageCount: Int = 0
    private var bugCount: Int = 0
    private var maxColSize = 0
    private var maxRowSize = 0

    /**
     * 입력값
     * 배추밭 배열, 배추 수
     */
    public fun solution(_farmArray: Array<Array<Boolean>>, _cabbageCount: Int): Int {
        this.farmArray = _farmArray
        this.cabbageCount = _cabbageCount

        this.farmArray.forEachIndexed { i, row ->
            row.forEachIndexed { j, it ->
                if (it) {
                    bugCount++
                    setBug(i, j)
                }
            }
        }

        return bugCount
    }

    public fun setMaxSize(x: Int, y: Int) {
        this.maxColSize = x
        this.maxRowSize = y
    }

    /**
     *
     * 재귀적으로 사방을 돌며 값을 셋팅한다.
     * 12 -> 3 -> 6 -> 9
     */
    private fun setBug(x: Int, y: Int) {

        farmArray[x][y] = false
        cabbageCount--

        if (cabbageCount == 0) {
            return
        }

        if (y >= 1 && farmArray[x][y - 1]) {
            setBug(x, y - 1)
        }
        if (x < maxColSize - 1 && farmArray[x + 1][y]) {
            setBug(x + 1, y)
        }
        if (y < maxRowSize - 1 && farmArray[x][y + 1]) {
            setBug(x, y + 1)
        }
        if (x >= 1 && farmArray[x - 1][y]) {
            setBug(x - 1, y)
        }

    }


}

/**
 * 전부
 */


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val exampleCount: Int = readLine().toInt()


    for (i in 1 .. exampleCount) {
        val baseData = readLine().split(" ").map { it.toInt() }
        val x = baseData[0]
        val y = baseData[1]
        val cnt = baseData[2]

        val arr = Array(x, { Array(y, { false }) })

        for (j in 0 until cnt) {
            val point = readLine().split(" ").map { it.toInt() }
            arr[point[0]][point[1]] = true

        }
        val sol = FarmAndBug()
        sol.setMaxSize(x,y)
        println(sol.solution(arr, cnt))
    }

}

배열값을 순회하며 해당 칸이 true인 경우 재귀적으로 탐색을 시작한다.

재귀를 시작하며 bugCount값을 하나 증가시킨다. 

 

재귀 시작

해당 칸은 검사가 끝났기때문에 false로 값을 변경한다.   

이후 상, 하 , 좌, 우 를 순차적으로 탐색하며 해당 값이 true인 경우 위의 단계를 동일하게 반복한다. 

마지막 단계인 우측을 검사하였을 때 사방이 fasle라면 해당 재귀를 종료한다. 

 

재귀가 끝난경우 다시 배열이동을 시작한다. 

 

만약 모든 배추를 검사한 경우(배추 카운트가 0인 경우) 

더이상의 탐색이 무의미하기에 무조건적으로 반복을 종료시킨다. 

 

최악의 경우 n*n 의 시간복잡도를 가질 것 이다.