[백준] 1113번 수영장만들기 코틀린

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

1113번: 수영장 만들기

 

처음 접근법: 완탐으로 4방향에 대해서 한방향씩 끝까지 탐색한다고 생각하고 각각의 타일에서 한번 더 2방향(내가 온 방향 및 그 반대 제외)을 끝까지 탐색해서 물이 세는지 확인, 4방향 각각의 최대값을 구하고 그 중에서 최소값이 시작타일의 높이보다 크다면 뺀 값이 물을 채울 수 있다는 아이디어 (틀림) -> 계속 물이 세는지 확인한다지만 예외적인 부분(탐색하지 않은 곳에서 물이 샐 수 있음)이 있어서 예제는 다 맞았지만 실패함.   

 

대표반례: 

5 5

55515

53121

54445

51115

55555 

답: 10

 

옳은 방법: (다른 블로그 보면서 참고한건데 정말 천재아닌가 싶다...ㅜㅜ) 물이 바깥으로 새어나가는 타일을 찾고 제외하는 것이 이번 문제의 핵심인데 반대로 생각해서 주어진 맵 전체를 둘러싸는 물탑(말 그대로 물로된 탑 높이 1~max까지)이 있다고 생각하고 바깥에서 안쪽으로 물을 집어넣는 것이 핵심이었다.

 

예를들어, 테두리에 높이 n의 물탑 형성(bfs) -> 맵에서 n보다 낮은 부분을 물탑을 형성하며(미리 만들고해도 상관x) bfs로 탐색 -> n보다 낮은 내부의 타일이 탐색되었다면 물이 샌다는 뜻 -> 물이 샌다는 뜻은 n높이 만큼의 물은 쌓일 수 없다는 것을 의미 -> 해당 타일의 높이를 n으로 만듬. -> n에 대한 bfs가 끝나면 전체탐색으로 n보다 낮은 타일은 물로 층을 하나 채워주고 결과값+1 (map[y][x]++, res++) -> res출력 [이를 n~입력에서 받은 최대높이까지 반복]

 

한마디로 높이 n위치의 물층을 쌓을 수 있는지 확인하기 위해서 바깥에서부터 물을 n위치에서 집어넣는다는 소리.

 

package bfs.advanced.b1113

import java.util.LinkedList

val br = System.`in`.bufferedReader()
val getLine get() = br.readLine().split(" ").map { it.toInt() }

var yy = 0
var xx = 0
fun isRange(y:Int,x:Int) = y in 0 until yy+2 && x in 0 until xx+2
lateinit var map: Array<IntArray>
lateinit var visited: Array<BooleanArray>
val que = LinkedList<P>()
var res = 0
var max = 0

val move = listOf(
    listOf(0,1),
    listOf(0,-1),
    listOf(1,0),
    listOf(-1,0),
    )

data class P(
    val y:Int,val x:Int
)

fun bfs(h: Int){
    visited = Array(yy+2){ BooleanArray(xx+2) } //독립시행을 위해 초기화
    visited[0][0] = true
    que.add(P(0,0))
    map[0][0] = h

    while (que.isNotEmpty()){
        val (y,x) = que.poll()

        for(r in 0..3){
            val dy = y+move[r][0]
            val dx = x+move[r][1]

            if(isRange(dy,dx) && !visited[dy][dx] && map[dy][dx] < h){ // 해당 높이보다 낮으면 물이 샌다는 뜻
                que.add(P(dy,dx))
                visited[dy][dx] = true
                map[dy][dx] = h //물이 샌다면 bfs 끝나고 완탐할 때 +1하지 않게 h로 높이 고정
            }
        }
    }
}

fun main(){
    getLine.let {
        yy = it[0]
        xx = it[1]
        map = Array(yy+2){ IntArray(xx+2) }

        for(y in 1 until yy+1){
            val p = br.readLine()
            for(x in 1 until xx+1) {
                max = maxOf(max,p[x-1].toString().toInt())
                map[y][x] = p[x-1].toString().toInt()
            }
        }

        for(h in 1..max) {
            bfs(h)

            for(y in 1 until yy+1)
                for(x in 1 until xx+1){
                    if(map[y][x] < h){ //물이 새지않고 (새었다면 높이가 h이므로 if문에 걸리지도 않음) , 물이 한층 더 쌓일 수 있는 곳은 물을 한층 쌓아준다.
                        res++
                        map[y][x]++
                    }
                }
        }

        println(res)
    }
}