백준 - 안전 영역(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

[문제 설명]

비가 오는 양에 따라 만들어지는 섬의 개수의 최댓값을 구하시오.

[접근 방법]

비는 0~최고높이-1까지 올 수 있다.

비가 안 오는 경우 섬의 개수는 최소 1이다.

최고 높이까지 오는 경우, 모두 물에 잠겨서 섬의 개수는 0이므로 체크할 필요가 없다.

따라서, 체크해야할 높이는 1~최고높이-1이 된다.

최저 높이부터 최고 높이까지 모든 경우를 BFS로 섬의 개수를 구하면 된다.

 

N은 2 이상 100 이하, 높이는 1이상 100이하이므로

시간복잡도는 N^2(전체 맵을 탐색하는데 비용)*H-1(최고 높이까지 확인해야하므로) ->O(N^2*(H-1))

-> 간략화하면 O(N^2*H) 

최악의 경우 맵의 크기가 100*100이고 최고 높이가 100이므로 ->100*100*100 -> 100^3 -> 10^6

-> 1,000,000

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList
import java.util.StringTokenizer

// BFS를 위한 큐. 매번 만들어줄 필요가 없으므로 탑 레벨에 선언.
val queue = LinkedList<IntArray>()
val directions = arrayOf(intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1))
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // 최대 섬개수는 비가 안왔을 때 1이 기본.
    // [S] 입력
    var cntOfMaxIsland = 1
    val N = readLine().toInt()
    val map = Array(N){IntArray(N)}
    var highestHeight = 0
    repeat(N) { idxOfRow ->
        val st = StringTokenizer(readLine(), " ")

        var idxOfCol = 0
        while (st.hasMoreTokens()) {
            val height = st.nextToken().toInt()
            map[idxOfRow][idxOfCol++] = height
            highestHeight = highestHeight.coerceAtLeast(height)
        }
    }
    // [E] 입력

    // 강수량
    var precipitation = 1
    // 최저 강수량 1부터 (최고 높이-1)까지 확인(최고 높이까지 비가오면 어차피 섬의 개수는 0이니까 확인 안함)
    while (precipitation < highestHeight) {
        cntOfMaxIsland = bfs(map, precipitation).coerceAtLeast(cntOfMaxIsland)
        // 현재 강수량은 체크했으므로, 강수량을 1높여서 체크
        precipitation++
    }

    println(cntOfMaxIsland)
}

fun bfs(map: Array<IntArray>, precipitation: Int): Int {
    val isVisited = Array(map.size){BooleanArray(map[0].size)}
    var cntOfIsland = 0

    for (row in map.indices) {
        for (column in map[row].indices) {
            // 높이가 강수량보다 높고, 방문하지 않았던 노드면 시작
            if (map[row][column] > precipitation && !isVisited[row][column]) {
                isVisited[row][column] = true
                queue.offer(intArrayOf(row, column))

                // BFS
                while (!queue.isEmpty()) {
                    val currentPosition = queue.poll()
                    for (idxOfDire in directions.indices) {
                        val nextPosition = intArrayOf(currentPosition[0]+directions[idxOfDire][0], currentPosition[1]+directions[idxOfDire][1])
                        // 다음 위치가 맵 안에 있고, 방문하지 않았고
                        if (nextPosition[0] in map.indices && nextPosition[1] in map.indices && !isVisited[nextPosition[0]][nextPosition[1]]) {
                            // 높이가 강수량보다 높으면 queue에 넣어서 BFS
                            if (map[nextPosition[0]][nextPosition[1]] > precipitation) {
                                queue.offer(nextPosition)
                            }
                            // 방문하지 않았는데 어차피 잠긴 땅이면 방문 처리.(다음에 방문하지 않게)
                            isVisited[nextPosition[0]][nextPosition[1]] = true
                        }
                    }
                }

                // row, column을 시작점으로 잡은 대륙은 전부 체크했으므로 +1
                cntOfIsland++
            }
        }
    }

    return cntOfIsland
}