[Kotlin] 백준 1926 그림 - BFS를 이용하여 문제 풀기

 

백준 예제에서 말하는 그림은 이렇게 총 4개를 말한다. (대각선으로 연결된건 떨어진것이다. )

참고설명

https://www.youtube.com/watch?v=ansd5B27uJM

너무 감사하게도 해당 예제로 BFS를 설명해주셨다. 이 분께서는 파이썬으로 해주셔서 내가 코틀린으로 알아서 고쳐서 작성했다. 

DFS와 BFS에 대한 설명도 이해하기 쉽게 설명해주셨으니 보는거 추천! 

전체 코드

fun main() {
    val (N, M) = readln().split(" ").map { it.toInt() }
    val inputArray = Array(N) { readln().split(" ").map { it.toInt() }.toIntArray() }
    val visited = kotlin.Array(N) { BooleanArray(M) }

    var count = 0
    var max = 0
    val dy = arrayOf(0, 1, 0, -1)
    val dx = arrayOf(1, 0, -1, 0)

    fun bfs(y: Int, x: Int): Int {
        var size = 1
        val queue: Queue<Pair<Int, Int>> = LinkedList()
        queue.add(Pair(y, x))

        while (queue.isNotEmpty()) {
            val (j, i) = queue.poll()
            for (k in 0 until 4) {
                val ny = j + dy[k]
                val nx = i + dx[k]

                if (ny in 0 until N && nx in 0 until M && inputArray[ny][nx] == 1 && !visited[ny][nx]) {
                    visited[ny][nx] = true
                    size++
                    queue.add(Pair(ny, nx))
                }
            }
        }
        return size
    } // bfs

    for (j in inputArray.indices) {
        for (i in inputArray[j].indices) {
            if (inputArray[j][i] == 1 && visited[j][i] == false) {
                //전체 그림 개수 +1
                visited[j][i] = true
                count += 1
                //BFS를 통해서 그림의 크기르 구한다.
                max = max(max, bfs(j, i))
                //최대값 갱신
            }
        }
    }
    println(count)
    println(max)
}

 

내가 궁금했던 점

1. 방문 여부를 어떻게 확인할 것인가? 

여기서 모두 false로 초기화 되어있다. for문을 돌면서 false이면 count를 플러스해주고 true로 변경하여 다시 순회 못하게끔 막는다. 

    val visited = kotlin.Array(N) { BooleanArray(M) }