[백준] 1012 - 유기농 배추

이전 2667-단지번호붙이기 문제와 동일한 풀이로 풀면 되는 BFS 문제.
주어지는 각 배추의 위치는 M-1, N-1 이기 때문에 0-based Index 로 풀어야한다.

필요한 벌레의 최소 숫자를 구해야하기 때문에 bfs 를 진입할 때 count 를 늘려야한다.

풀이

/*
* 무방향 비연결 그래프
* 첫째줄 테스트케이스 개수 T
* 둘째줄 배추밭 가로길이 M (1 ~ 50), 세로길이 N (1~50), 배추 심어진 개수 K(1 ~ 2500)
*
* 그 다음 K줄에 배추 위치 X(0~ M-1), Y(0~ M-1). 두 배추의 위치가 같은 경우는 없음
*
* 출력 - 각 테스트 케이스 별 최소의 배추흰지렁이 마리 수 출력
*
* BFS. 실행 시 count 증가
*
* O(t) * O(M*N)
* */

private val dx = intArrayOf(-1, 1, 0, 0)
private val dy = intArrayOf(0, 0, -1, 1)
private lateinit var visitedArr: Array<BooleanArray>
private lateinit var farmArr: Array<IntArray>

var m = 0
var n = 0

fun `1012-유기농 배추`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val t = br.readLine().toInt()
    val stringBuilder = StringBuilder()

    // 0-based Index
    repeat(t){
        var warmCount = 0
        val token = StringTokenizer(br.readLine())

        // 초기화
        m = token.nextToken().toInt()
        n = token.nextToken().toInt()
        val k = token.nextToken().toInt()

        farmArr = Array(m){ IntArray(n) }
        visitedArr = Array(m){ BooleanArray(n) }

        repeat(k){
            val token = StringTokenizer(br.readLine())
            farmArr[token.nextToken().toInt()][token.nextToken().toInt()] = 1
        }

        for(i in 0 until m){
            for(j in 0 until n){
                if(farmArr[i][j] == 0 || visitedArr[i][j]) continue

                /*
                * 벌레 카운트 증가
                * */
                warmCount++
                bfs(i, j)
            }
        }

        if(stringBuilder.isNotEmpty()) stringBuilder.append("\n")
        stringBuilder.append("$warmCount")
    }

    bw.write(stringBuilder.toString())
    bw.flush()
    bw.close()
    br.close()
}

private fun bfs(startX: Int, startY: Int){
    val arrayDeque = ArrayDeque<Pair<Int, Int>>()

    arrayDeque.addLast(startX to startY)
    visitedArr[startX][startY] = true

    while (arrayDeque.isNotEmpty()){
        val from = arrayDeque.removeFirst()
        val x = from.first
        val y = from.second

        /*
        * 연결된 x, y 에 방문한다.
        * */
        for(i in 0 until 4){
            val nx = x + dx[i]
            val ny = y + dy[i]

            if(nx in 0 until m && ny in 0 until n && farmArr[nx][ny] == 1 && !visitedArr[nx][ny]){
                visitedArr[nx][ny] = true
                arrayDeque.addLast(nx to ny)
            }
        }
    }
}

후기

이전 문제를 풀어서 그런지, 금방 풀었다.
그다지 어렵지 않았음.