[백준] 물채우기 (시뮬레이션)

문제 소개

물채우기 - 백준 17621번 문제를 정리합니다.
이 문제는 격자 형태의 막힌 칸들을 고려해, 물을 부었을 때 고이는 칸의 총 개수를 구하는 문제입니다.

문제의 핵심은 "세로로 연결된 막힌 칸 덩어리"와 "그 덩어리가 바닥에 붙었는지 여부"를 구분하고, 이를 바탕으로 물이 고이는 높이를 양쪽에서 갱신하며 계산하는 것입니다.

문제 링크: 물채우기 - 백준 17621번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 각 열에 있는 막힌 칸 정보를 바탕으로 바닥에 붙은 덩어리인지 판단
2. 바닥에 붙은 덩어리 기준으로 왼쪽 → 오른쪽, 오른쪽 → 왼쪽으로 스캔하며 물의 최소 고임 높이를 갱신
3. 공중에 뜬 덩어리는 서로 인접한 열끼리 연결되어 있다면 한 그룹으로 보고, 양 방향에서 다시 스캔
4. 위 정보를 바탕으로 물 고임 높이 계산 → 전체 고인 칸 개수 계산

---

해결 과정 및 코드

핵심 아이디어

1. 각 열마다 막힌 칸의 시작과 끝 좌표를 받아 Column 객체로 저장
2. 바닥에 붙은 덩어리만 따져서 좌우로 스캔하면서 waterH0를 갱신
   → 이는 바닥과 연결된 칼럼의 고임 가능 최대 높이로 간주
3. 공중에 뜬 덩어리는 isNotLink 함수를 통해 연속한 공중 덩어리 그룹을 탐색한 뒤,
   그 범위에 대해서만 다시 좌우로 waterH1 갱신
4. 이후 waterH0, waterH1 값을 바탕으로 물이 고이는 칸 개수를 세기
   • 바닥 연결된 경우: startY - waterH0
   • 공중 덩어리: (startY - waterH1) + (N+1 - waterH0) − (겹치는 영역 제외)

코드

시간 복잡도 : O(M)
이유: 각 열을 한 번만 순회하며 조건 비교 및 스캔 연산 수행 (M ≤ 100,000)

 

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

public class Main {
	public static class Column {
		int startY, endY;
		int waterH0, waterH1; // 배열 대신 개별 변수 사용

		public Column(int startY, int endY) {
			this.startY = startY;
			this.endY = endY;
			this.waterH0 = 0;
			this.waterH1 = 0;
		}
	}

	static Column[] columns;
	static int N, M;

	public static void main(String[] args) throws IOException {
		N = read();
		M = read();
		columns = new Column[M];

		for (int i = 0; i < M; i++) {
			int startY = read();
			int endY = read();
			if (endY == 0) {
				startY = N + 1;
				endY = N + 1;
			}
			columns[i] = new Column(startY, endY);
		}

		// 바닥에 붙어있는 덩어리만 고려하여 물이 고이는 높이 계산
		calcWaterH(0, M, 1, 0);  // left -> right
		calcWaterH(M - 1, -1, -1, 0);  // right -> left

		// 공중에 뜬 덩어리만 고려하여 물이 고이는 높이 계산
		calcFloatingWaterH();

		// 물이 고이는 칸의 총 개수 계산
		System.out.println(calcTotalWater());
	}

	private static void calcWaterH(int start, int end, int dir, int target) {
		int min = N + 1;
		for (int cur = start; cur != end; cur += dir) {
			if (target != 0 || columns[cur].endY >= N) {
				min = Math.min(min, columns[cur].startY);
			}
			if (target == 0) {
				columns[cur].waterH0 = Math.max(min, columns[cur].waterH0);
			} else {
				columns[cur].waterH1 = Math.max(min, columns[cur].waterH1);
			}
		}
	}

	private static void calcFloatingWaterH() {
		for (int start = 0; start < M; ) {
			if (columns[start].endY >= N) {
				start++;
			} else {
				int end = start + 1;
				for (; end < M; end++) {
					if (isNotLink(end, end - 1)) {
						break;
					}
				}
				calcWaterH(start, end, 1, 1);
				calcWaterH(end - 1, start - 1, -1, 1);
				start = end;
			}
		}
	}

	private static boolean isNotLink(int a, int b) {
		return (columns[a].startY > columns[b].endY || columns[a].endY < columns[b].startY);
	}

	private static long calcTotalWater() {
		long sum = 0;
		for (int cur = 0; cur < M; cur++) {
			if (columns[cur].endY >= N) {
				sum += columns[cur].startY - columns[cur].waterH0;
			} else {
				sum += columns[cur].startY - columns[cur].waterH1;
				sum += N + 1 - columns[cur].waterH0;

				int underWaterH = Math.max(columns[cur].waterH0, columns[cur].waterH1);
				if (underWaterH <= columns[cur].endY) {
					sum -= (columns[cur].endY - underWaterH + 1);
				}
			}
		}
		return sum;
	}

	public static int read() throws IOException {
		int cur, n = System.in.read() & 15;
		boolean isNegative = (n == 13);
		if (isNegative) {
			n = System.in.read() & 15;
		}
		while ((cur = System.in.read()) > 32) {
			n = (n << 3) + (n << 1) + (cur & 15);
		}
		return isNegative ? ~n + 1 : n;
	}
}

참고

비슷한 문제 유형이지만, 물채우기는 공중에 뜬 벽에 있어서 빗물과 같은 방식으론 해결할 수 없었습니다.

2025.06.26 - [Algorithm] - [백준] 빗물 (투 포인터)

[백준] 빗물 (투 포인터)