(코틀린) BOJ14719 빗물

협회: https://www.acmicpc.net/problem/14719

소스 코드(구현)

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
import kotlin.math.abs

//(1 ≤ H, W ≤ 500)
private var H = 0 //세로
private var W = 0 //가로
private var answer = 0
private lateinit var map :List<Int>
private lateinit var isVisited :BooleanArray
private fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    br.readLine().split(" ").map { it.toInt() }.apply {
        H = this(0)
        W = this(1)
    }
    //0이상 H이하의 정수 W개 (블록이 쌓인 높이를 의미하는 수 주어짐)
    map = br.readLine().split(" ").map { it.toInt() }
    isVisited = BooleanArray(W) { false }

    for (i in H downTo 1){
        val indexList = mutableListOf<Int>()
        for (k in map.indices){
            if (map(k) >= i){
                indexList.add(k)
            }
        }
        getWaterSpace(indexList, i)
    }

    println(answer)
}

private fun getWaterSpace(indexList :List<Int>, targetH :Int){
    if (indexList.size <= 1) return
    var p1 = indexList(0)
    var p2 = indexList(1)
    //두개의 인덱스 사이에 있는 애들 전부 Visited 처리 (기둥의 인덱스는 포함하지 않음)
    for (i in 2..indexList.size){
        if (abs(p2-p1) != 1){
            for(k in minOf(p1,p2)+1 ..maxOf(p1,p2)-1){
                if (!isVisited(k)){
                    answer += targetH - map(k)
                    isVisited(k) = true
                }
            }
        }
        //두개의 포인터중 숫자가 작은 포인터가 값 바뀜
        if (i > indexList.lastIndex) break
        if (p1 > p2) p2 = indexList(i) else p1 = indexList(i)
    }
}

해결책:

맨 위에서 시작하여 해당 열 값으로 웅덩이를 만들 수 있는지 검색합니다.

높이가 4인 두 개의 열이 있는 경우 두 열 사이의 각 간격은

높이의 수역을 생성합니다(4 – 그들 사이의 기둥 높이).
웅덩이를 만든 경우 isVisited를 확인하고 선택하지 않은 영역이 있는지 다시 확인합니다.

높이가 1이 될 때까지