백준 - 유기농 배추(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/1012

 

[문제 설명]

배추밭에 벌레가 몇마리가 필요한지 묻는 문제.

 

[접근 방법]

그래프에 부분트리가 몇개 있는지 묻는 문제 같다.

처음엔 맵을 전부 체크하면서 BFS하는 코드를 작성했다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

val directions = arrayOf(intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1))
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val T = readLine().toInt()
    for (noOfTestcases in 0 until T) {
        val input = readLine().split(" ").map{it -> it.toInt()}
        val lenOfColumn = input[0]
        val lenOfRow = input[1]
        val cntOfCabbage = input[2]
        val map = Array(lenOfRow) { BooleanArray(lenOfColumn) }
        var answer = 0

        for (cabbage in 0 until cntOfCabbage) {
            val position = readLine().split(" ").map{it -> it.toInt()}
            map[position[1]][position[0]] = true
        }

        for (row in 0 until lenOfRow) {
            for (column in 0 until lenOfColumn) {
                if (map[row][column]) {
                    map[row][column] = false
                    answer++

                    val position = intArrayOf(row, column)
                    bfs(position, map)
                }
            }
        }

        println(answer)
    }
}

fun bfs(position: IntArray, map: Array<BooleanArray>) {
    val queue = LinkedList<IntArray>()
    queue.offer(position)
    while (!queue.isEmpty()) {
        val currentPosition = queue.poll()
        for (direction in directions) {
            val nextPosition = intArrayOf(currentPosition[0]+direction[0], currentPosition[1]+direction[1])
            if (nextPosition[0] in 0..map.lastIndex && nextPosition[1] in 0..map[0].lastIndex) {
                if (map[nextPosition[0]][nextPosition[1]]) {
                    queue.offer(nextPosition)
                    map[nextPosition[0]][nextPosition[1]] = false
                }
            }
        }
    }
}

이렇게 되면 O(정점의개수)이 복잡도가 되므로, O(NM)이 된다.

 

이를 보완하기 위해, 양배추가 있는 곳만 검색하는 코드를 작성했다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

val directions = arrayOf(intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1))
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val T = readLine().toInt()
    for (noOfTestcases in 0 until T) {
        var neededInsectCnt = 0
        val input = readLine().split(" ").map{it -> it.toInt()}
        val lenOfColumn = input[0]
        val lenOfRow = input[1]
        val cntOfCabbage = input[2]
        val map = Array(lenOfRow) { BooleanArray(lenOfColumn) }
        val arrOfCabbagePosition = Array(cntOfCabbage) {IntArray(2)}

        for (cabbage in 0 until cntOfCabbage) {
            val position = readLine().split(" ").map{it -> it.toInt()}
            arrOfCabbagePosition[cabbage][0] = position[1]
            arrOfCabbagePosition[cabbage][1] = position[0]
            map[position[1]][position[0]] = true
        }

        arrOfCabbagePosition.forEach { positionOfCabbage ->
            if (map[positionOfCabbage[0]][positionOfCabbage[1]]) {
                map[positionOfCabbage[0]][positionOfCabbage[1]] = false
                neededInsectCnt++

                val position = intArrayOf(positionOfCabbage[0], positionOfCabbage[1])
                bfs(position, map)
            }
        }

        println(neededInsectCnt)
    }
}

fun bfs(position: IntArray, map: Array<BooleanArray>) {
    val queue = LinkedList<IntArray>()
    queue.offer(position)
    while (!queue.isEmpty()) {
        val currentPosition = queue.poll()
        for (direction in directions) {
            val nextPosition = intArrayOf(currentPosition[0]+direction[0], currentPosition[1]+direction[1])
            // 다음 이동 좌표가 범위 밖이 아니면
            if (nextPosition[0] in 0..map.lastIndex && nextPosition[1] in 0..map[0].lastIndex) {
                if (map[nextPosition[0]][nextPosition[1]]) {
                    queue.offer(nextPosition)
                    map[nextPosition[0]][nextPosition[1]] = false
                }
            }
        }
    }
}

양배추에 위치를 담을 배열 arrOfCabbagePosition을 만들었고, 이 영역만 검색하기로 했다.

시간복잡도는 O(K)가 되지 않을까 싶다.