[백준/Swift] 14719 : 빗물 문제 뿌수기!! ( 2개 반례 포함)

 

 

• BOJ_14719.swift

• 14719 : 빗물/ 문제 소개
• 풀이 과정
• 코드 구현

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

14719 : 빗물/ 문제 소개

 

물이 고일 수 있는 경우는 빈 블럭보다 높은 블럭이 양 옆에 혹은 떨어져서 존재해야 물은 고일 수 있다.

평평하거나 높이가 0인 경우 물은 고이지 않는다.

풀이 과정

 

주어진 2차원 세계에서

그림 1. 좌 힌트1, 우 힌트 2

바닥은 항상 막혀있다.

 

빗물이 고이는 경우는 힌트 1과 힌트 2에 답이 있다.

• 첫번째, 둘러 쌓여 있는 겉 블록의 양 끝 높이가 같거나 오른쪽이 클 경우

그림2

이 경우 힌트의 동그라미 분홍색 칠과 같은 경우이다.

가장 왼쪽 블록과 가장 오른쪽 블록의 높이가 같거나 오른쪽 블록의 높이가 클때 왼쪽 블록을 기준으로 빗물이 고이는 경우를 구하는 것이다.

• 두번째, 둘러 쌓여 있는 겉 블록의 형태에서 왼쪽 블록의 높이가 오른쪽 블록의 높이보다 큰 경우이다.

그림 3

이 경우 그림 2와는 반대로 오른쪽 블록의 높이를 기준으로 둘러 쌓인 블록 안에 고인 물을 구해야 한다.

---

처음 문제를 풀어 나갈 때는 막연하게 그림 1. 우 힌트 2의 문제를 기준으로

둘러 쌓인 왼쪽 블럭보다 오른쪽 블록이 클 때 양 쪽 블록 사이의 블록들의 물이 고인느 블록을 카운트하고 왼쪽 블록을 오른쪽 블록으로 치환하고 문제를 풀어 나갔고 마지막에서야 그림 3의 경우처럼 블록이 작을 때를 비교했습니다.

즉 width가 주어졌을 때 그림1처럼 비교를 계속 해 나가다 마지막width-1일때만 작은 경우를 비교했다는 사실.. O(N^2)

---

이 문제를 틀린 후에 물이 고일 수 있는 경우의 수를 위와 같이 두 가지로 분리하고 문제를 풀어나갔습니다.

그리고 "투 포인터"라는 개념을 새로 배웠습니다.  O(N)

(queue처럼 배열을 훑을 수 있는 2개의 포인터를 사용하는데 사용되는 의미가 다릅니다.)

---

문제에서 width만큼의 높이가 주어지는데

위에서 정의한 빗물이 고이는 경우 첫번째, 두번째를 차례대로 체크해 주면 높이에서 물이 고일 수있는 최대 블록 개수가 나옵니다.

 

for i in 0..<width까지 포문을 탐색하면서

빗물이 고이는 경우 첫번째가 완벽하게 실행된다고 가정하고 맨 왼쪽의 블록 높이를 기준으로 다음 탐색 블록의 높이 차이가 낮을 때

기준 높이 - 현재 탐색중인 블록 높이

차이를 더해가며 문제를 풀어나갑니다.

만약 기준이 되는 맨 왼쪽 블록의 높이보다 오른쪽 블록의 높이가 높은 경우에는 기준이 되는 블록의 높이를 그 오른쪽 블록의 높이로 설정하고 풀어나갑니다.

실제로 왼쪽 블록이 오른쪽 블록과 같아지는 경우가 있을 때는 위에서 가정하면서 고인 물을 구해 나간 sum이 사실이 됩니다.

그럼 지금까지 가정하면서 구한 고인 물의 높이들을 answer라는 변수에 담고 

다시 sum을 0으로 초기화 하고 둘러 쌓일 블록의 높이 맨 왼쪽 높이를 노란색으로 색칠된 블록으로 정하고 계속해서 탐색을 이어 나갑니다.

 

만약 탐색을 다 완료했는데 같거나 큰 오른쪽 블록을 발견하지 못했다면, 위에서 가정한 조건이 거짓이므로 구한 sum은 정답이 아니고 0처리를 합니다.

---

이번엔 반대로 둘러 쌓일 블록의 맨 오른쪽 높이를 width -1로 설정하고 거꾸로 맨 왼쪽의 블록 높이 index까지 탐색을 이어나갑니다.

기준이되는 오른쪽 블록보다 작은 블록이 있을 경우는 물이 무조건 고인 경우입니다. 왜냐하면 둘러 쌓인 맨 왼쪽 블록이 무조건 크기 때문입니다. 

여기서 자신보다 큰 블록이 나온다면 둘러 쌓이 블록의 맨 오른쪽 높이를 그 블록으로 설정하고 계속해서 탐색해나가면 답이 나옵니다.

 

다음은 반례입니다.

제가 구현한 코드가 틀렸다는 것을 알게된 반례는

 

3 3

3 2 1

ans = 0 wrong = 1

 

7 10

5 7 4 3 2 5 6 4 1 2

ans = 11 

코드 구현

 

import Foundation

func BOJ_14719()
{
    let hw = readLine()!.split(separator:" ").map{Int(String($0))!}
    let block = readLine()!.split(separator:" ").map{Int(String($0))!}
    
    let (height,width) = (hw[0],hw[1])
    var sum = 0 ,ans = 0
    var left = 0 ,right = 0
    /*
     처음에는 둘러 쌓일 맨 왼쪽 블록이 맨 오른쪽 블록과 같거나 큰 블록이 존재한다는 가정하에
     맨 왼쪽 블록 높이를 기준으로 고인 물을 탐색해 나간다.
     그러다 정말 발견하면 둘러쌓여있는 형태이므로 지금까지 구한 sum을 ans에 더하고 다시 둘러 쌓일 맨 왼쪽 블록의 높이를 둘러 쌓인 맨 오른쪽 블록 높이로 지정하고 위와 같은 연산을 반복.
     */
    for i in 0..<width
    {
        if block[left] > block[i]
        {
            sum += block[left] - block[i]
        }
        else if block[left] <= block[i]
        {
            ans += sum
            sum = 0
            left = i
        }
    }
    right = width - 1
    //만약 위에서 한 가정이 거짓인,, 둘러쌓일 맨 오른쪽 블록 높이가 맨 왼쪽 블록 높이보다 낮다면!!
    //꺼꾸로 탐색을 이어나간다..
    while(left < right)
    {
        for i in stride(from:right,through: left, by: -1)
        {
            if block[right] <= block[i]
            {
                right = i
            }
            else
            {
                ans += block[right] - block[i]
            }
        }
    }
    print(ans)
}
BOJ_14719()

 

visit my github