[BOJ] 빗물 14719.JAVA

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

이 문제의 등급이 골드 5라서 문제를 읽기도 전에 겁을 먹었다..

그래도 스터디 시간에 풀어야 하기 때문에 문제 풀기 시작했고 생각했던 것보다 어렵지 않아 빠른 시간 안에 해결했다.

어려운 문제라고 생각했는데 내가 의도한 대로 문제가 잘 풀려나가서 최근 문제 풀면서 가장 크게 뿌듯함을 느끼게 해준 문제다.

내가 구현한 핵심 로직은 각 행의 막혀있는 지점의 위치를 찾아서 반복문을 통해 1번 지점과 2번 지점 사이의 공간에 물을 채우는 로직이다.

아래와 같이 소스를 공유한다.

public class 빗물 {
	public static class Node {
		int x, y;
		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		
		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);
		
		int[][] map = new int[n][m];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int idx = 0;
		while(st.hasMoreTokens()) {
			int y = Integer.parseInt(st.nextToken());
			for(int i = 0; i <= y-1; i++) {
				map[i][idx] = 1;
			}
			idx++;
		}
		
		for(int i = 0; i < n; i++) {
			List<Node> list = new ArrayList<>();
			for(int j = 0; j < m; j++) {
				if(map[i][j] == 1) {
					list.add(new Node(i, j));
				}
			}
			
            // 행에 벽이 2개 이상일때 벽과 벽 사이의 공간에 빗물(2) 채우기
			if(list.size() >= 2) {
				for(int j = 0; j < list.size()-1; j++) {
					for(int k = list.get(j).y+1; k < list.get(j+1).y; k++) {
						map[i][k] = 2;
					}
				}
			}
			list = new ArrayList<>();
		}
		
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				int v = map[i][j];
				if(v == 2) cnt++;
			}
		}
		
		System.out.println(cnt);
	}
}