[알고리즘] 백준 14719 빗물 / 자바

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

14719번: 빗물

 

나름의 규칙성(?)을 찾아서 map을 모두 탐색 하면서 계산했다.

map에 블록을 1로 저장해놓고, 행을 차례대로 탐색했다.

여기서 블록으로 저장된 1과 빈공간 0이 연속되고 + 블록을 다시 만날 때까지 while문을 돌았을 때, 빗물은 고일 수 있다.

블록에서 시작해 블록을 다시 만나는 그 사이의 0 개수가 빗물의 양이다.

벽을 만나지 못하고 W 범위를 넘어가면 더하지 않고 넘어갔다.

import java.util.*;
import java.io.*;
public class Main_14719 {
    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[][] map = new int[H][W];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            int start = H - Integer.parseInt(st.nextToken());
            for (int j = start; j < H; j++) {
                map[j][i] = 1;
            }
        }
        
        int result = 0;
        // map 모두 탐색
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W-1; j++) {
                if (map[i][j] == 1 && map[i][j+1] == 0) {   // 블록 빈 공간이 연속이면
                    int count = 0;
                    while (true) {
                        j++;
                        if (j == W) {   // 블록을 만나지 못해서 빗물 고일 수 X
                            break;
                        }
                        if (map[i][j] == 1) {   // 블록 만나서 빗물 고임
                            result += count;
                            j--;
                            break;
                        }
                        count++;
                    }
                }
            }
        }
        
        System.out.println(result);
    }
}