[백준] 알고리즘 분류(구현,JAVA)14719번, 빗물

문제 링크

14719번: 빗물

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 2차원 세계에 바닥은 막혀있다.

2. 2차원 세계에 빗물이 고이는 양을 결과로 출력합니다.

3. 빗물은 블럭 사이에서 고인다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 열마다 빗물이 고이는 양을 탐색합니다.

 

3. 빗물이 고인 양을 모두 더한 값을 결과로 출력합니다.

 

 

빗물 고이는 양 탐색

 

빗물이 고이려면 기본적으로 자신의 높이보다 높은 블럭에 둘러져있어야 합니다.

 

빗물 고이는 조건!

 

※ 1번째 열과 마지막 열은 물이 고일 수 없습니다!

 

1. 열 기준 좌측으로 자신보다 높은 블럭이 존재할 때

2. 열 기준 우측으로 자신보다 높은 블럭이 존재할 때

 

조건에 만족할 때 빗물 고이는 양 계산

 

좌측 가장 높은 블럭, 우측 가장 높은 블럭 중 더 작은 높이 만큼 빗물이 고입니다.

 

Why?

 

빗물? : X		블럭
블럭	빗물	블럭
블럭	빗물	블럭
블럭	블록	블럭

 

더 높은 블럭을 기준으로는 낮은 블럭 방향으로 빗물이 고이지 않고 흘러내려가기 때문입니다.

 

결과적으로 위에 예제에서

 

좌측 블록 최대 높이 : 3우쪽 블록 최대 높이 : 4

 

더 작은 블록의 높이 = 좌측 블록 최대 높이 = 3

 

해당 열의 고이는 물의 양 : 좌측 블록 최대 높이 - 해당 열 블록의 높이 = 3 - 1 = 2

 

2만큼 물이 고입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

H : 4

W : 4

 

높이

3 0 1 4

 

2. 각 열마다 빗물이 고이는 양을 탐색합니다.

※ 1번째 열과 마지막 열은 물이 고일 수 없습니다!

 

빗물 고이는 양 탐색!

 

2번째 열

 

좌측 블럭 최대 높이 : 3

우측 블럭 최대 높이 : 4

고이는 물의 양 : 좌측 블럭 최대 높이 - 현재 열 블록 높이 = 3 - 0 = 3

 

3번째 열

좌측 블럭 최대 높이 : 3

우측 블럭 최대 높이 : 4

 

고이는 물의 양 : 좌측 블럭 최대 높이 - 현재 열 블록 높이 = 3 - 1 = 2

 

3. 빗물이 고인 양을 모두 더한 값을 결과로 출력합니다.

 

2번째 열 : 3

3번째 열 : 2

 

빗물 고인 양 더하기 : 2 + 3 = 5

 

5을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 블럭의 높이를 띄어쓰기 기준 나누었습니다.
• 좌측, 우측 블럭 높이에 따라 2~(W-1)열의 고인 빗물의 양을 구합니다.
• 고인 빗물의 양 모두 더한 값을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        int[] height = new int[W];	//블럭 높이 저장 배열
        int answer = 0;
        //블럭 높이 저장
        for(int i=0;i<W;i++)
            height[i] = Integer.parseInt(st.nextToken());

        //2번째 열부터 마지막 전 열까지 빗물 모이는 양 계산
        for(int i=1;i<W-1;i++){
            int left = 0, right = 0;	//좌측, 우측 최대 높이 블럭 변수
            //좌측 블럭 최대 높이 구하기
            for(int j=0;j<i;j++)
                left = Math.max(left, height[j]);
            //우측 블럭 최대 높이 구하기
            for(int j=i+1;j<W;j++)
                right = Math.max(right, height[j]);
            //현재 열 블럭이 좌측, 우측 블럭보다 작을 때
            if(height[i] < left && height[i] < right){
            	//고인 빗물 계산
                answer += Math.min(left, right) - height[i];
            }
        }
        bw.write(answer + "");	//고인 모든 빗물 양 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}