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

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

2468번: 안전 영역

 

난이도 : 실버 1
태그 : 그래프 이론, 깊이 우선 탐색, 너비 우선 탐색, 브루트포스, 그래프 탐색

 

 

설명

비가 오는 양에 따라 잠기는 지역이 있을 수도 있고, 없을 수도 있습니다.

높이는 1이상 100 이하 이므로,

1~100 높이 모두를 대상으로 DFS 혹은 BFS를 진행해 안전구역의 최대 개수를 구하면 됩니다

DFS, BFS 중 어느 것을 사용해도 무방하나, 저는 BFS를 사용하여 풀이하였습니다.

 

 

소스코드

import java.util.LinkedList
import java.util.Queue
import java.util.StringTokenizer
import kotlin.math.max

fun main(): Unit = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val dx = arrayOf(0, 0, 1, -1)
    val dy = arrayOf(1, -1, 0, 0)

    val map = Array(n) { Array(n) { 0 } }
    repeat(n) { x ->
        val st = StringTokenizer(readLine())
        repeat(n) { y ->
            map[x][y] = st.nextToken().toInt()
        }
    }

    var maxCnt = 0
	
    // 빗물의 높이 0부터 100까지 모든 높이에 대해 탐색
    for (height in 0..100) {
        var cnt = 0

        val visited = Array(n) { Array(n) { false } }

		// 모든 지점에 대해 BFS 수행
        repeat(n) { x ->
            repeat(n) { y ->
                if (visited[x][y] || map[x][y] <= height) return@repeat

                cnt++

                val q = LinkedList<Pair<Int, Int>>() as Queue<Pair<Int, Int>>
                q.offer(Pair(x, y))
                visited[x][y] = true

                while (q.isNotEmpty()) {
                    val target = q.poll()

                    for (i in 0 until 4) {
                        val nx = target.first + dx[i]
                        val ny = target.second + dy[i]

                        if (nx !in 0 until n || ny !in 0 until n || visited[nx][ny] || map[nx][ny] <= height) continue

                        q.offer(Pair(nx, ny))
                        visited[nx][ny] = true
                    }
                }
            }
        }

        maxCnt = max(maxCnt, cnt)
    }

    println(maxCnt)
}

 

다소 복잡해보일 수 있지만,

최외곽 for문은 0부터 100까지의 높이 모두에 대한 탐색,

안쪽 repeat 두개는 모든 좌표에 대해 BFS를 수행하는 반복문입니다.

 

 

후기

처음봤을 땐, 어떻게 풀어야 하나 고민했는데,

높이가 1부터 100까지 밖에 되지 않길래, 모든 높이에 대해 연산을 수행해 풀 수 있었습니다.