[백준 알고리즘] 14719번 자바(Java) 빗물

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

 

풀이

• 시간복잡도, 메모리
  • 모든 칸을 확인한다는 점에서 O(H*W), 즉 2만5천이 된다
  • boolean형 2단 배열[500][500], 충분히 커버
• 풀이과정
  • 첫시도 스택: 왼쪽 제일 큰 수를 통해서 할려했으나 완전히 잘못된 생각 → 당연히 틀림
  • 이후에 블록으로 표시된 곳은 true로 표시하고 모든 층을 반복문돌려서 해당층의 왼쪽 시작점과 오른쪽 시작점을 찾는 방식을 생각해봤다
  • 이후 조건에 맞게 왼쪽 시작점과 오른쪽 시작점을 찾으면 그 사이에 있는 방문하지않은 칸을 더해준다.(방문했다는것은 블록인칸 따라서 제외)
• 그림 풀이

처음에 방문체크
false false false true
true  false false true
true  false false true
true  false true  true
  3     0    1      4

 

 

 

 

 

예제 입력 예시

4 8
3 1 2 3 4 1 1 2

 

예제 출력 예시

5

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//14719번
//미리 블록의 위치를 방문체크해두고 각 층마다 2개가 있으면 사이에 존재하는 칸(방문하지않은칸)을 체크

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());
        boolean[][] blocked = new boolean[H][W];

        //쌓여있는 블록 체크
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            int height = Integer.parseInt(st.nextToken());
            for (int j = 0; j < height; j++) {
                blocked[j][i] = true;
            }
        }

        int waterfallCnt = 0;
        //블럭 제외 빗물가능 체크
        for (int i = 0; i < H; i++) {
            int leftBlock = -1;
            int rightBlock = -1;
            //좌측 가장 바깥 블록 체크
            for (int j = 0; j < W; j++) {
                if(blocked[i][j]){
                    leftBlock = j;
                    break;
                }
            }
            //우측 가장 바깥 블록 체크
            for (int j = W-1; j >=0 ; j--) {
                if(blocked[i][j]) {
                    rightBlock = j;
                    break;
                }
            }

            //해당 층에 블락 2개 없는경우 제외, 같은 위치인경우 제외
            if(leftBlock == -1 || rightBlock == -1 || leftBlock == rightBlock) continue;
            //사이에 있는 칸 갯수 체크
            for (int j = leftBlock+1; j <rightBlock; j++){
                if(!blocked[i][j])waterfallCnt++;
            }
        }
        System.out.println(waterfallCnt);
    }
}

 

 

 

 

문제 출처

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

14719번: 빗물