[백준] 14719. 빗물 (자바 JAVA)

[ 문제 ]  BOJ 14719. 빗물

 

문제 링크 : https://www.acmicpc.net/problem/14719

14719번: 빗물

 

 

 

---

# 접근 방법 및 풀이 

 

• 그냥 구현! 이문제 보니 스택으로 많이 풀었던데, 난 그냥 문제대로 구현했다.
• 이 문제를 보고 스택을 바로 안 떠올렸는데 이런거 보면 자료구조 형태의 문제 유형에 부족하다는 것을 느꼈다.
• 무튼 나는 첫번째 만나는 블록, 그리고 빈칸에 대한 flag를 두어서 구현했다. 입력에서 모든 블록은 map에서 1로 표현했다.
• 그리고 map의 가장 아래행 부터 탐색하며 빗물이 고일 수 있다면 cnt를 센다.
• 첫번째 블록을 발견했을 때 block true, 첫번째 블록을 발견한 상태에서 빈칸을 발견하면 빈칸 can true, 그리고 그때부터 빈칸의 cnt를 하나씩 센다. 
• 칸수를 세어도 빗물이 고이기 위해선 양옆이 막혀있어야 되기 때문에, 두개의 flag가 true이고 map을 탐색하며  map[i][j] = 1인 경우, 막혀있기 때문에 그때 cnt를 ans에 더한다. 

# 주의할 점 

 

• 두개의 flag 변수를 다시 false로 초기화 해주는 부분이다. 나는 당연히 ans에 cnt를 더해주고 둘다 false처리를 했는데, 첫번째 블록 flag는 초기화 해줄 필요가 없다. map[i][j]가 1일때 블록이기 때문에 그 블록이 다시 양옆 블록에서 왼쪽에 위치하기 때문이다. 
• 말로 설명하기 어렵지만, 1 0 1 0 1 인경우를 생각해보면 된다.

 

JAVA 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class bj14719_빗물 {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int map[][] = new int[H][W];
		st = new StringTokenizer(in.readLine());
		for (int j = 0; j < W; j++) {
			int num = Integer.parseInt(st.nextToken());
			for (int i = H-1; i >= H - num; i--) {
				map[i][j] = 1;
			}
		}
		int ans = 0;
		for (int i = H-1; i >= 0; i--) {
			int cnt = 0;
			boolean block = false;
			boolean can = false;
			for (int j = 0; j < W; j++) {
				if(!block && map[i][j] == 1) {
					block = true;
				}
				if(block && map[i][j] == 0) {
					cnt++;
					can = true;
				}
				if(block && can && map[i][j] == 1) {
					ans += cnt;
					cnt = 0;
					can = false;
				}
			}
		}
		System.out.println(ans);
	}
}

 

 

 

REVIEW

한번만에 맞추자..