[BOJ 8982] 수족관 1 (Java)

BOJ 8982 수족관 1

문제풀이

처음에는 수족관 모양 그대로 만들어서 정말 물을 빼고 세어보는 시뮬레이션을 생각했는데 메모리 제약이 128MB인데 수족관의 크기는 최악의 경우에 int[40001][40001]이기 때문에 불가능하다는 것을 깨달았다.

이 문제는 특별한 알고리즘을 사용하기 보다는 물이 빠졌을 때 해당 열의 수족관 높이와 수면의 높이에 집중해야한다. 높이는 모두 row 값으로 기록한다.

• 주어진 데이터를 입력받아 각 열의 수족관 깊이를 기록한다.
• 각 배수구를 중심으로 좌, 우로 수면의 높이를 갱신해나간다.
  • 해당 열의 수면이 배수구 높이보다 낮으면 현재 배수구 높이로 갱신한다.
  • 현재 배수구 높이 보다 높은 높이가 나타나면 더 높은 높이로 진행한다.
• 각 열에 남은 물은 해당 열의 높이 - 수면의 높이다.

구현코드

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

public class Main {
	
	static class Node {
		int r, c;
		
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	
	static final int MAX = 40001;
	static int[] surface, depth;
	static Node[] hole;
	static int N, K, ans, lastIdx;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = stoi(br.readLine());
		
		ans = 0;
		surface = new int[MAX];
		depth = new int[MAX];
		
		// 각 열에 대한 수족관 깊이를 입력한다.
		// 0, 0 제거 
		br.readLine();
		for(int i = 0 ; i < N / 2 - 1 ; ++i) {
			st = new StringTokenizer(br.readLine());
			int x1 = stoi(st.nextToken());
			int y1 = stoi(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			int x2 = stoi(st.nextToken());
			int y2 = stoi(st.nextToken());

			for(int j = x1 ; j <= x2 ; ++j) {
				depth[j] = y1;
			}
			
			lastIdx = x2 - 1;
		}
		// 마지막 제거 
		br.readLine();
		
		K = stoi(br.readLine());

		// 수족관 배수구 데이터 입력 
		hole = new Node[K];
		for(int i = 0 ; i < K ; ++i) {
			st = new StringTokenizer(br.readLine());
			int idx = stoi(st.nextToken());
			int dep = stoi(st.nextToken());
			hole[i] = new Node(dep, idx);
		}
		
		for(Node cur : hole) {
			int curDepth = cur.r;
			int col = cur.c;
			
			// 왼쪽으로 갱신 
			for(int i = col ; i >= 0 ; --i) {
				// 현재 깊이를 최소값으로 유지한다. 
				curDepth = curDepth > depth[i] ? depth[i] : curDepth;
				surface[i] = curDepth > surface[i] ? curDepth : surface[i];
			}
			
			curDepth = cur.r;
			col = cur.c;
			
			// 오른쪽으로 갱신 
			for(int i = col ; i <= lastIdx ; ++i) {
				// 현재 깊이를 최소값으로 유지한다. 
				curDepth = curDepth > depth[i] ? depth[i] : curDepth;
				surface[i] = curDepth > surface[i] ? curDepth : surface[i];
			}
			
		}
		
		for(int i = 0 ; i <= lastIdx ; ++i) {
			ans += depth[i] - surface[i];
		}
		
		System.out.println(ans);
	}
	
	private static void print() {
		for(int i = 0 ; i <= lastIdx ; ++i) {
			System.out.print(depth[i] + " ");
		}
		System.out.println();
		for(int i = 0 ; i <= lastIdx ; ++i) {
			System.out.print(surface[i] + " ");
		}
		System.out.println();
		System.out.println();
	}
	
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}