[Algorithm/Java] 백준 14719번 - 빗물

---

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

---

🔍 문제 풀이

문제 도식화

배운 점

처음에는 2차원 배열을 선언하고,
각 열마다 블록의 높이만큼 1을 채우는 방식으로 시뮬레이션을 시도했다.

이후 위에서 아래로 내려가면서 빈 칸(0)을 기준으로 양옆이 벽(1)으로 막혀 있는지를 판단하여,
물이 고이는 위치를 찾으려 했다.

하지만 직접 구현해보니,

1. 블록 위아래 구조를 체크해야 하고
2. 각 줄마다 경계를 확인해야 하며
3. 범위 설정이 복잡해지는 문제점이 있었다.

결국, 구글 서치를 통해 이 문제는 2차원 배열이 아니라 1차원 배열로도 해결이 가능하다는 사실을 알게 되었다.

입력 배열이 각 열의 블록 높이를 나타내므로,
현재 위치를 기준으로 왼쪽과 오른쪽의 최대 높이만 알면 고일 수 있는 물의 양을 계산할 수 있었다.

앞으로는 더 단순한 방식이 있는지 먼저 고민해보는 습관을 들여야 겠다.

💻 전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        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[] arr = new int[w];


        // 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < w; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int result = 0;
        // 맨 왼쪽과 맨 오른쪽 벽을 제외
        for(int i=1; i< w-1; i++) {
            int left = 0;
            int right = 0;

            // 왼쪽 최대
            for (int j = 0; j < i; j++) {
                left = Math.max(left, arr[j]);
            }

            // 오른쪽 최대
            for (int j = i+1; j < w; j++) {
                right = Math.max(right, arr[j]);
            }
            int water = Math.min(left, right) - arr[i];
            if (water > 0) result += water;


        }
        System.out.println(result);

    }
}