[백준/BOJ] 2468번: 안전 영역

출처

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

2468번: 안전 영역

해설

모든 지역이 물에 잠길 때까지 반복을 하며 안전한 영역이 가장 많을 때의 수를 구하면 된다.

때문에 입력을 받으면서 가장 높은 지역의 높이를 구해놓는다.

ex) 최대높이 5 -> 0 ~ 5를 반복

 

각 지역에서 비가 온 만큼의 값을 빼준 후 bfs를 돌릴까 생각했지만, 이보다 비가 온 양보다 지역의 높이가 높을 때를 생각해주는 것이 더 편할 것 같았다.

따라서 if(arr[i][j] >= height && !visited[i][j])일 때 bfs를 돌려 안전한 영역을 구해주었다.

 

주의할 점으로는 문제의 노트 부분을 보면 "아무 지역도 잠기지 않을 수 있다."라는 말이 있다.

위에서 말했듯 0부터 반복을 하면 상관없지만, 

나는 처음에 비가 무조건 온다는 가정 하에 1부터 반복을 하여 76퍼에서 틀렸습니다를 받았다.

문제는 끝까지 읽어야 한다.

소스 코드

import java.util.*

private var n = 0
private lateinit var arr: Array<IntArray>
private lateinit var visited: Array<BooleanArray>
private val que: Queue<Pair<Int, Int>> = LinkedList()
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var high = Integer.MIN_VALUE
private var low = Integer.MAX_VALUE

fun main() {
    input()
    if(high == 1) {
        println(1) 
        return
    }
    println(submerge())
}

private fun input() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    arr = Array(n) { IntArray(n) }
    visited = Array(n) { BooleanArray(n) }

    repeat(n) { i ->
        val st = StringTokenizer(readLine())
        repeat(n) { j ->
            arr[i][j] = st.nextToken().toInt()
            high = maxOf(high, arr[i][j])
            low = minOf(low, arr[i][j])
        }
    }
}

private fun submerge(): Int {
    var maxArea = 0
    for(i in low until high) {
        resetVisited()
        maxArea = maxOf(maxArea, safeAreaCount(i))
    }

    return maxArea
}

private fun safeAreaCount(height: Int): Int {
    var cnt = 0
    repeat(n) { i ->
        repeat(n) { j ->
            if(arr[i][j] > height && !visited[i][j]) {
                cnt++
                que.add(Pair(i, j))
                bfs(height)
            }
        }
    }

     return cnt
}

private fun bfs(height: Int) {
    while(que.isNotEmpty()) {
        val cur = que.poll()
        for(i in 0 until 4) {
            val nextY = cur.first + dy[i]
            val nextX = cur.second + dx[i]

            if(!rangeCheck(nextY, nextX, height)) continue

            visited[nextY][nextX] = true
            que.add(Pair(nextY, nextX))
        }
    }
}

private fun rangeCheck(y: Int, x: Int, height: Int): Boolean {
    if(y !in 0 until n || x !in 0 until n  || arr[y][x] <= height || visited[y][x]) return false
    return true
}

private fun resetVisited() {
    repeat(n) { i ->
        repeat(n) { j ->
            visited[i][j] = false
        }
    }
}