문제
N x M 격자의 높이가 주어질 때, 물을 채울 수 있는 최대 부피를 구하라. 가장자리로 물이 빠지면 채울 수 없다.
입력
첫째 줄에 N, M, 이후 N줄에 높이가 주어진다.
출력
채울 수 있는 물의 양을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 5 16661 61116 16661 | 4 |
풀이
높이 1부터 9까지 BFS로 같은 높이 영역을 탐색하며, 가장자리에 닿지 않는 웅덩이에 물을 채운다.
- 높이 k=1부터 9까지 순회하며 높이 k인 미방문 칸을 BFS로 탐색한다
- BFS 중 가장자리에 도달하거나 더 낮은 인접 칸이 있으면 물이 빠진다(flood)
- 물이 빠지지 않으면 인접한 더 높은 칸의 최소 높이까지 물을 채우고 높이를 갱신한다
- 모든 높이에 대해 반복한다
핵심 아이디어: 낮은 높이부터 채우면 물이 차오르는 과정을 시뮬레이션할 수 있으며, 가장자리 연결 여부로 물 유출을 판단한다.
코드
package day799;
import java.io.*;
import java.util.*;
public class Day771BOJ1113수영장만들기 {
static int N, M, ans;
static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[][] board = new int[N][M];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < M; j++) {
board[i][j] = s.charAt(j) - '0';
}
}
boolean[][] v = new boolean[N][M];
for (int k = 1; k <= 9; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] == k && !v[i][j]) {
v[i][j] = true;
BFS(new int[] { i, j }, board, v, k);
}
}
}
}
System.out.println(ans);
}
public static void BFS(int[] start, int[][] board, boolean[][] v, int num) {
Queue<int[]> q = new LinkedList<int[]>();
q.add(start);
List<int[]> candi = new ArrayList<int[]>();
candi.add(start);
int minHeight = Integer.MAX_VALUE;
boolean flood = false;
while (!q.isEmpty()) {
int[] now = q.poll();
if (now[0] == 0 || now[0] == N - 1 || now[1] == 0 || now[1] == M - 1) {
flood = true;
}
for (int d = 0; d < 4; d++) {
int nx = now[0] + dx[d];
int ny = now[1] + dy[d];
if (0 <= nx && nx < N && 0 <= ny && ny < M) {
if (!v[nx][ny] && board[nx][ny] == num) {
v[nx][ny] = true;
q.add(new int[] { nx, ny });
candi.add(new int[] { nx, ny });
}
if (board[nx][ny] < num) {
flood = true;
}
if (board[nx][ny] > num) {
minHeight = Math.min(minHeight, board[nx][ny]);
}
}
}
}
if (!flood) {
ans += candi.size() * (minHeight - num);
for (int i = 0; i < candi.size(); i++) {
int[] now = candi.get(i);
board[now[0]][now[1]] = minHeight;
v[now[0]][now[1]] = false;
}
}
}
}복잡도
- 시간: O(9 * N * M)
- 공간: O(N * M)