[백준][코틀린][16946] 벽 부수고 이동하기 4

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

16946번: 벽 부수고 이동하기 4

문제 풀이

1. 주어진 문제를 전체 탐색을 하면서 벽을 하나씩 부수고 BFS 를 수행할 경우 시간 초과가 발생한다. O(N^2 * M^2)

2. BFS 를 수행할 때 이동이 가능한 영역(0)에 대해서 그룹화하여 각 그룹의 개수를 저장한다.

3. 각 그룹의 개수를 저장하는 groupMap 을 선언한다.

4. 결과를 출력한다. 이때 N, M 만큼 탐색하여 map[X][Y] 가 1이고 group[X][Y] 가 0인 영역의 상하좌우 인접한 그룹의 개수를 더한다.

5. 4번과정을 수행할 경우 시간초과가 발생한다. 아래와 같은 경우 동일한 그룹에 대해서 개수를 더할 필요가 없다.

(0, 0) 의 인접한 위치인 오른쪽과 아래쪽 영역은 같은 그룹이기 때문에 한 번만 더해야 한다. 따라서 중복을 피할 수 있게 Set 을 선언해서 중복 그룹인지를 확인 한다.

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val map = Array(N) { br.readLine().map { it - '0' }.toIntArray() }

    // 0인 지역으로 그룹으로 구분하기 위해 BFS 를 수행한다.
    val group = Array(N) { IntArray(M) { 0 } }
    val groupMap = IntArray(500001) { 0 }
    var groupNum = 1

    for (i in 0 until N) {
        for (j in 0 until M) {

            // 0인 영역이면서 group 이 지정안된 곳을 찾는다.
            if (map[i][j] == 0 && group[i][j] == 0) {
                groupMap[groupNum] = bfs(N, M, map, group, i, j, groupNum)
                groupNum++
            }
        }
    }

    /*group.forEach { _group ->
        _group.forEach { g ->
            print("$g ")
        }
        println("")
    }*/


    for (i in 0 until N) {
        for (j in 0 until M) {
            if (map[i][j] == 1 && group[i][j] == 0) {
                //인접한 영역의 중복 그룹인지 확인하는 용도의 set
                val set = mutableSetOf<Int>()
                //상하좌우 인접한 영역 확인
                val dX = intArrayOf(-1, 1, 0, 0)
                val dY = intArrayOf(0, 0, -1, 1)
                for (k in 0..3) {
                    val newX = i + dX[k]
                    val newY = j + dY[k]

                    //영역 밖.
                    if ((newX < 0 || newX >= N) || (newY < 0 || newY >= M)) continue
                    //벽으로된 영역
                    if (map[newX][newY] == 1) continue
                    //이미 탐색한 그룹
                    if (set.contains(group[newX][newY])) continue

                    //println("($newX, $newY) ${group[newX][newY]}, ${groupMap[group[newX][newY]]}")

                    set.add(group[newX][newY])
                    map[i][j] += groupMap[group[newX][newY]]
                }
            }
        }
    }

    val result = StringBuilder()

    map.forEach { _map ->
        _map.forEach { m ->
            result.append("${m % 10}")
        }
        result.append("\n")
    }

    println(result.toString())
}

private fun bfs(N: Int, M: Int, map: Array<IntArray>, group: Array<IntArray>, x: Int, y: Int, num: Int): Int {
    val queue = LinkedList<Pair<Int, Int>>()
    queue.add(Pair(x, y))
    group[x][y] = num
    var cnt = 1

    while (queue.isNotEmpty()) {
        val (curX, curY) = queue.pop()

        val dX = intArrayOf(-1, 1, 0, 0)
        val dY = intArrayOf(0, 0, -1, 1)

        for (i in 0..3) {
            val newX = curX + dX[i]
            val newY = curY + dY[i]

            //영역 밖.
            if ((newX < 0 || newX >= N) || (newY < 0 || newY >= M)) continue
            // 이미 grouping 된 영역.
            if (group[newX][newY] > 0) continue
            // 벽.
            if (map[newX][newY] == 1) continue

            cnt++
            group[newX][newY] = num
            queue.add(Pair(newX, newY))
        }
    }
    return cnt
}