[백준] 14719번 빗물 자바

문제

 

14719번: 빗물

 

 

문제 풀이

 

✔️ 알고리즘

1. 빗물 block[][] 배열에 받아두기

2. block배열의 맨 아래 행부터 위로 올라가면서 고인 빗물세기

3. 블록 처음 만났을 경우, 빗물이 고일 수 있으므로 start변수에 true로 설정해두기

4. start변수가 true이면서 다시 블록을 만났을 경우 end변수에 true로 설정하기

5. 그리고 다시 빈 곳을 만났을 경우 end변수 false로 바꾸기

6. 한 행의 반복이 끝났는데 end변수가 true가 아니라면 빗물이 고일 수 없으므로 해당 구간은 카운트하지 않음

 

 

 

소스 코드

 

import java.util.Scanner;

public class b_14719 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int answer = 0, count;
		boolean start = false, end = false;	//블록 시작하고 닫히는 거 체크할 플래그 변수
		int H = sc.nextInt();
		int W = sc.nextInt();
		int[][] block = new int[H][W];
		
		for(int i = 0; i < W; i++) {
			int rain = sc.nextInt();
			int idx = H-1;
			for(int j = 0; j < rain; j++) {
				block[idx--][i] = 1;
			}
		}
		
		/* 빗물 확인
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++)
				System.out.print(block[i][j]);
			System.out.println();
		}*/
			
		for(int i = H-1; i >= 0; i--) {		//맨 아래 줄 부터
			start = false;
			end = false;
			count = 0;
			for(int j = 0; j < W; j++) {	//가로로 빗물 세기
				//블록일 경우
				if(block[i][j] == 1) {
					if(!start)
						start = true;
					else
						end = true;
				}
				//블록이 아닐 경우
				else {
					if(end) {
						end = false;
						answer += count;
						count = 0;
					}
					if(start && !end)
						count++;
				}
			}
			if(!end)
				continue;
			answer += count;
		}
			
		System.out.println(answer);
	}
}