[BOJ] 14719: 빗물 (JAVA)

문제

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

 

여담

좀 복잡하게 풀었다는 생각이 들어 다른 풀이를 참고했더니 역시 더 쉬운 방법이 있었다...^^

 

시간 차이는 크게 나지 않았지만 다른 방법으로 풀어보니 확실히 내가 풀었던 방법이 더욱 복잡했다는 것을 깨달았다. 언제쯤 정석 풀이로 풀까..ㅎㅎ 그래도 풀었다는 것에 의의를 둬야지!

위: 간단한 버전, 아래: 복잡한 버전

 

풀이

간단한 버전이 정석으로 푸는 방법 같아서, 간단한 버전에 대해서만 설명을 진행하겠다.

 

빗물이 고이려면 현재 블록의 높이보다 높은 블록들로 둘러쌓여야 한다. 따라서 현재 블록의 왼쪽과 오른쪽을 탐색해야 한다.

 

즉, 빗물이 고이기 위해서는 다음의 조건을 모두 만족해야 한다.

• 현재 블록의 왼쪽에 자신보다 높은 블록이 존재하는 경우
• 현재 블록의 오른쪽에 자신보다 높은 블록이 존재하는 경우

 

따라서 다음과 같이 각 블록을 기준으로 왼쪽/오른쪽에 위치하는 블록의 최대 높이를 구해서 고이는 빗물의 양을 구하면 된다.

• 현재 블록의 왼쪽에 위치하는 블록들 중 최대 높이 구하기
  • 현재 블록의 위치가 i일 때, 왼쪽에 위치하는 블록 j의 범위는 0 ~ i - 1
  • 최대 높이 구하기: leftHeight = Math.max(leftHeight, heights[j])
• 현재 블록의 오른쪽에 위치하는 블록들 중, 최대 높이 구하기
  • 현재 블록의 위치가 i일 때, 오른쪽에 위치하는 블록 j의 범위는 i + 1 ~ W - 1
  • 최대 높이 구하기: rightHeight = Math.max(rightHeight, heights[j])
• 현재 블록의 높이가 왼쪽의 최대 높이와 오른쪽의 최대 높이보다 작아야 빗물이 고임
  • 빗물이 고이는 경우: heights[i] < leftHeight && heights[i] < rightHeight
  • 고이는 빗물의 양은 Min(왼쪽 최대 높이, 오른쪽 최대 높이) - 현재 블록 높이

 

주의해야 할 것은 첫 번째 열과 마지막 열에는 빗물이 고일 수 없다는 것이다. (그림에서 막혀있는 것처럼 보이지만 그러한 조건은 주어지지 않았다..!)

 

코드

풀이 1 (간단한 버전)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int[] heights = new int[W];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < W; i++) {
            heights[i] = Integer.parseInt(st.nextToken());
        }

        int totalRain = 0;
        for (int i = 1; i < W - 1; i++) { // 양 끝 블록에는 물이 고일 수 없음 (벽 역할을 해줘야 함)
            int leftHeight = 0, rightHeight = 0; // 현재 블록을 기준으로, 왼쪽/오른쪽에 위치하는 블록의 최고 높이
            // 왼쪽 찾기
            for (int j = 0; j < i; j++) {
                leftHeight = Math.max(leftHeight, heights[j]);
            }

            // 오른쪽 찾기
            for (int j = i + 1; j < W; j++) {
                rightHeight = Math.max(rightHeight, heights[j]);
            }

            // 현재 블록의 높이가 왼쪽/오른쪽에 위치하는 블록의 최고 높이보다 낮다면
            if (heights[i] < leftHeight && heights[i] < rightHeight) { // 빗물이 고일 수 있음
                totalRain += Math.min(leftHeight, rightHeight) - heights[i];
            }
        }
        System.out.println(totalRain);
    }
}

 

풀이 2 (복잡한 버전)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int[] heights = new int[W];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < W; i++) {
            heights[i] = Integer.parseInt(st.nextToken());
        }

        int totalRain = 0, i = 0;
        while (i < W - 1) {
            boolean isFind = false;
            for (int j = i + 1; j < W; j++) {
                if (heights[i] <= heights[j]) { // 현재 블록 높이보다 크거나 같은 블록을 찾은 경우
                    for (int k = i + 1; k < j; k++) { // 그 사이에 고이는 빗물의 양 구하기
                        totalRain += heights[i] - heights[k];
                    }
                    i = j;
                    isFind = true;
                    break;
                }
            }

            if (!isFind) { // 현재 블록 높이보다 큰 것이 없다면, 높이를 낮춰서 찾아보기
                heights[i]--;
            }
        }
        System.out.println(totalRain);
    }
}

---

참고

https://tussle.tistory.com/979