[Kotlin, S1] 백준 2468번 안전 영역

출처: unsplash.com

 

안전 영역(2468번)

Silver 1

#그래프 이론 #브루트포스 알고리즘 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색

 

문제 내용

 

문제 접근

n * n의 영역에서 내리는 비의 양에 따라서 잠기는 영역이 생기게 된다.

영역이 3일 때, 비의 양이 3 이상이면 모든 영역 3이 잠기게 된다.

 

영역의 개수는 상하좌우에 붙어있는 모든 안전 영역들은 하나로 간주한다.

대각선의 안전 영역은 모두 별개의 안전 영역이 된다.

 

내리는 비의 양에 따라 잠기는 영역의 수가 달라지게 될 것이다.

물에 잠기지 않은 영역의 수의 최대 개수를 구한다.

 

비의 양은 영역에서 가장 작은 값에서부터 가장 큰 값까지 정의하고 탐색해 보면 될 거라고 생각하기 쉽다.

하지만 영역에서 가장 큰 값으로 구해봤자 모든 영역이 잠기게 되기 때문에 굳이 구할 필요는 없고, 비가 오지 않는 경우도 있기 때문에 비가 오지 않은 케이스인 0부터 정의하고 구해야 할 것이다.

결론은 비의 양은 0부터 높이 정보 중 가장 큰 값 - 1까지 모두 확인해 잠기지 않은 영역의 최댓값을 구한다.

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

private var map = arrayOf<List<Int>>()
private var visited = arrayOf(booleanArrayOf())
private val dx = listOf(-1, 1, 0, 0)
private val dy = listOf(0, 0, -1, 1)

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val n = bf.readLine().toInt()
    map = Array(n) { listOf() }
    visited = Array(n) { BooleanArray(n) }

    var maxH = 0
    for (i in 0 until n) {
        val ln = bf.readLine().split(" ").map { it.toInt() }
        map[i] = ln

        maxH = max(maxH, ln.max())
    }

    var answer = 0
    for (h in 0 until maxH) {
        var safeArea = 0

        for (i in visited.indices) {
            visited[i].fill(false)
        }

        for (i in map.indices) {
            for (j in map[i].indices) {
                if (!visited[i][j] && map[i][j] > h) {
                    visited[i][j] = true
                    safeArea++
                    dfs(j, i, h)
                }
            }
        }

        answer = max(answer, safeArea)
    }

    println(answer)
}

private fun dfs(x: Int, y: Int, h: Int) {
    for (i in dx.indices) {
        val mx = dx[i] + x
        val my = dy[i] + y

        if (my in map.indices && mx in map[my].indices) {
            if (!visited[my][mx] && map[my][mx] > h) {
                visited[my][mx] = true
                dfs(mx, my, h)
            }
        }
    }
}

 

문제 풀이

입력받으면서 가장 높은 영역을 구해준다.

그리고 dfs를 이용해 침수되지 않는 영역의 개수를 구해준다.

 

반복문을 통해 비의 양(h)에 따른 모든 case를 검사한다.

침수되지 않은 영역을 구하고 나면, answer에서 더 큰 값으로 변경한다.

visited 여부와 h보다 높이가 높은지 확인한다.

 

 

문제 해결 과정

비가 오지 않는 경우를 확인하지 않았기 때문에 69%에서 WA가 나왔다.

그 외에는 어려운 점이 없었다.

 

체감 난이도: Silver 1