[BOJ] 백준 14719번 : 빗물 자바 (JAVA)

Junseong·2021년 12월 31일

알고리즘

1. 문제

백준 14719번 빗물 - https://www.acmicpc.net/problem/14719

✅ 알고리즘 분류 - 구현, 시뮬레이션

🥇 난이도 - Gold 5

2. 풀이

이 문제는 시뮬레이션 문제여서 구현하는 방법이 여러가지가 있을 수 있지만 저는 다음과 같이 구현하였습니다.

주어진 입력을 2차원 배열로 나타낸다.
2차원 배열의 각 행마다 다음과 같은 작업을 수행한다.
행의 첫 번째 열 부터 마지막 열까지 탐색을 하면서 블록이 놓아져 있는지 확인한다.
만약 블록이 놓아져있다면 해당 행에서 처음 등장한 블록인지 아닌지 확인한다.
처음 등장한 블록이라면 빗물이 고일 구역의 왼쪽 블록이 될 수 있으므로 해당 열을 left로 설정한다.
처음 등장한 블록이 아니라면 빗물이 고일 구역의 오른쪽 블록이 될 수 있으므로 해당 열을 right로 설정한다.
해당 행에서 두 블록 사이에 고일 빗물의 수인 right-left-1 값을 결과에 더해준다.
기존의 오른쪽 블록이 이제는 빗물이 고일 왼쪽 블록이 될 수 있기 때문에 right를 left로 바꿔준다.

이해를 돕기 위해 그림을 통해 설명드리겠습니다.

입력이 1 4 0 1 3 3 1 1 1 2 로 들어온 경우 이를 2차원 배열로 나타내면 아래와 같습니다.

그리고 빗물이 고인 모습은 아래와 같을 겁니다.

첫 번째 행을 살펴보면 1의 위치에 블록이 처음 등장합니다.

1의 위치에 있는 블록은 빗물이 고일 왼쪽 블록이 될 수 있기 때문에 left로 지정해 줍니다. (left = 1)

남은 열을 확인해보니 빗물이 고일 오른쪽 블록이 없기 때문에 해당 행에는 빗물이 고일 수 없습니다.

두 번째 행을 살펴보면 1의 위치에 블록이 처음 등장하고 4,5 위치에 블록이 존재합니다.

1의 위치에 있는 블록은 빗물이 고일 왼쪽 블록이 될 수 있기 때문에 left로 지정해 줍니다. (left = 1)

그다음 4의 위치에 있는 블록은 오른쪽 블록이 될 수 있기 때문에 right로 지정해 줍니다. (right = 4)

left와 right가 지정되면 결과에 right-left-1을 더해줍니다. (결과 = 2)

이제 right였던 블록이 빗물이 고일 왼쪽 블록이 될 수 있기 때문에 left로 지정해 줍니다. (left = 4)

그 다음으로 등장하는 5의 위치에 있는 블록은 빗물이 고일 오른쪽 블록이 될 수 있기 때문에 right로 지정해 줍니다. (right = 5)

마찬가지로 left와 right가 지정되면 결과에 right-left-1을 더해줍니다.

right였던 블록이 빗물이 고일 왼쪽 블록이 될 수 있기 때문에 left로 지정해 줍니다. (left = 5)

사실 left와 right 사이에 공간이 없어 빗물이 고일 수 없기 때문에 의미없는 과정이고 별도의 조건문으로 건너뛸 수 있겠지만 코드의 간결성과 일관적인 처리를 위해 저는 건너뛰지 않았습니다.

세 번째 행을 살펴보면 1의 위치에 블록이 처음 등장하고 4,5,9 위치에 블록이 존재합니다.

5의 위치에 블록이 left가 될때까지 두 번째 행과 동일한 작업이 수행되어집니다. (결과 = 4)

그 다음으로 등장하는 9의 위치에 있는 블록은 빗물이 고일 오른쪽 블록이 될 수 있기 때문에 right로 지정해 줍니다. (right =9)

결과에 right-left-1을 더해줍니다. (결과 = 7)

네 번째 행을 살펴보면 2의 위치에만 블록이 없습니다.

앞에서 설명드린 과정을 수행하면 최종적으로 다음과 같은 상태가 되고 결과값이 정답이 됩니다. (결과 = 8)

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        st = new StringTokenizer(br.readLine());
        boolean[][] map = new boolean[h][w];

        //입력 처리
        for (int c=0; c<w; c++) {
            int b = Integer.parseInt(st.nextToken());
            for (int r=0; r<b; r++) map[h-r-1][c] = true;
        }

        int result = 0;
        for (int r=0; r<h; r++) {
            int left = 0;
            boolean flag = false;
            for (int c=0; c<w; c++) {
                if (map[r][c]) {
                    if (flag) result += c-left-1;
                    else flag = true;
                    left = c;
                }
            }
        }

        System.out.println(result);
    }
}