협회: https://www.acmicpc.net/problem/14719
14719호: 빗물
첫 번째 줄은 2D 세계의 세로 길이 H와 2D 세계의 너비 W를 제공합니다.
(1 ≤ H, W ≤ 500) 두 번째 줄에는 2D 세계에서 가장 왼쪽 위치인 블록의 높이를 나타내는 0과 H 미만의 정수가 있습니다.
www.acmicpc.net
소스 코드(구현)
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이 될 때까지