[백준, 1113, 자바] 수영장 만들기

https://www.acmicpc.net/problem/1113

1113번: 수영장 만들기

1. 문제 핵심

1. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직유면제 취의 표면에는 물이 없다.
2. 땅의 높이는 0이고, 땅은 물을 무한대로 흡수할 수 있다.

---

 

 

2. 문제 접근

접근법 1.

1. 한 노드부터 BFS로 주변 노드를 검사.
2. 해당 노드의 높이보다 낮은 노드가 있으면 수영장이 될 수 없다고 판단.
3. 가장자리와 맞닿아있으면 물이 새기 때문에 수영장 불가 판단.
4. visit 배열로 같은 높이의 노드를 기록하고 2,3번 조건이 만족되면 수영장이 될 수 있다 판별해서 한 칸씩 높임.
5. 현재 노드에서 BFS를 반복해서 높이가 주변 최대 높이의 노드와 같아질 때까지 반복.
6. 모든 칸을 순회하면서 1~5번 반복

 

 

결론
예제는 모두 통과했지만 40% 언저리에서 메모리 초과 발생.

 

---

접근법 2. (효율성 증가)

1. 동일
2. 동일
3. 동일
4. 같은 높이의 노드를 순회하는 동시에 주변 노드 검사를 통해 더 높은 노드 중 가장 낮은 노드를 기록.
5. visit배열에 기록된 같은 높이의 노드의 높이를 기록한 최대 최소 높이로 변경.
6. 현재 노드에서 BFS를 반복해서 높이가 주변 최대 높이의 노드와 같아질 때까지 반복
7. 모든 칸을 순회하며 1~6번 반복

결론

제한 메모리인 128MB를 초과했지만 자바여서 통과

 

---

접근법 3. (가지치기 추가)

1. 동일
2. 동일
3. 동일
4. 같은 높이의 노드를 순회하는 동시에 주변 노드 검사를 통해 더 높은 노드 중 가장 낮은 노드를 기록.
5. visit배열에 기록된 같은 높이의 노드의 높이를 기록한 최대 최소 높이로 변경.
6. 현재 노드에서 BFS를 반복해서 높이가 주변 최대 높이의 노드와 같아질 때까지 반복
7. 검사했을 때 해당되지 않는 배열과 물을 채운 위치를 기록해두고 이후 순회할 때 해당 칸들은 검사하지 않음.

결론

메모리를 대폭 줄이고 시간을 절반정도 낮출 수 있었음.

 

---

3. 코드 분석

 

 

 

4. 문제 후기

BFS탐색을 통한 간단한 시뮬레이션 문제이지만 감이 떨어져서인지 가지치기에 대한 부분을 너무 안일하게 생각해서 메모리 초과가 발생했습니다.

또한, 코테 연습을 위해 디버거를 사용하지 않고 풀려고 했으나 메모리 초과 문제를 해결하기 위해 여러 부분에서 메모리 효율성을 위한 코드를 추가 작성하다보니 생각치 못한 사이드 이펙트가 발생해서 시간을 잡아먹은 끝에 디버깅을 했습니다.

---

5. 자바 코드

import java.util.*;
import java.io.*;


public class Main {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);

		byte read() throws IOException {
			if (bufferPos == bufferState) {
				bufferState = dis.read(buffer, bufferPos = 0, bfs);

				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];

		}

		int nextInt() throws IOException {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}

		String readLine() throws IOException {
			int cnt = 0;
			byte c;
			byte[] tmp = new byte[bfs];
			while ((c = read()) != ' ') {
				if (c == '\n' || c == '\r') {
					if (cnt != 0)
						break;
					else
						continue;
				}
				tmp[cnt++] = c;
			}
			return new String(tmp, 0, cnt);
		}
	}

	public static void main(String[] args) throws IOException {
		Reader br = new Reader();
		Queue<int[]> q = new LinkedList<>();
		int row = br.nextInt();
		int col = br.nextInt();

		int crntY, crntX, nextY, nextX, cnt = 0, fstLv, ans = 0, ceilHeight;
		int[] crntQ;
		int[][] bd = new int[row][col],
				// 상, 우, 하, 좌
				dydx = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
		char[] each;

		//방문검사 배열을 2개 생성
		//1. 수영장 물을 넣었거나 아예 검사 불가능한 타일을 저장하는 배열
		boolean[][] visitPerma = new boolean[row][col];
		//2. 새로운 물을 넣기 위해 매번 초기화되는 방문 배열
		boolean[][] visitTmp = new boolean[row][col];
		//더 낮은 위치가 존재하거나 외곽과 맡닿아있는지 확인
		boolean isOuter;
		//데이터 입력
		for (int i = 0; i < row; i++) {
			each = br.readLine().toCharArray();
			for (int j = 0; j < col; j++) {
				bd[i][j] = each[j] - '0';
			}
		}

		//모든 노드 순회하며 검사
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				
				//이전에 처리한 노드면 검사 X
				if (visitPerma[i][j])
					continue;
				//해당 위치에서 더 이상 물을 넣을 수 없을 때까지 반복해서 물을 넣음
				while (true) {
					// 현재 지역보다 높은 땅 중 가장 낮은 값을 구하기 위해
					ceilHeight = Integer.MAX_VALUE;

					// 외곽지역 닿은지 알 수 없기 때문에 초기화
					isOuter = false;

					// 시작 위치 트루
					visitTmp[i][j] = true;
					// 물을 채웠다면 높이가 계속 변하기 때문에 최신 값
					fstLv = bd[i][j];
					q.add(new int[] { i, j });

					// 한 번에 몇개가 체크가 되었는지 확인
					cnt = 1;
					// bfs로 가장 낮은 땅부터 한줄씩 물을 다 깔아봄
					Outer: while (!q.isEmpty()) {
						crntQ = q.poll();
						crntY = crntQ[0];
						crntX = crntQ[1];

						// 네방향
						for (int l = 0; l < 4; l++) {
							nextY = crntY + dydx[l][0];
							nextX = crntX + dydx[l][1];

							// 외곽과 닿아있는 부분
							if (nextY < 0 || nextY == row || nextX < 0 || nextX == col) {
								isOuter = true;
								break Outer;
							}

							// 방문을 했다면 건너띔
							else if (visitTmp[nextY][nextX])
								continue;

							// 첫 검사자리보다 더 낮은 자리라면 물이 내려가기때문에 탈출
							else if (bd[nextY][nextX] < fstLv) {
								isOuter = true;
								break Outer;
							}

							// 나보다 높은 땅인데
							else if (bd[nextY][nextX] > fstLv) {
								// 그중 가장 낮은 땅인 경우
								if (ceilHeight > bd[nextY][nextX])
									ceilHeight = bd[nextY][nextX];
								continue;
							}

							// 나랑 높이 같은 땅을 카운팅
							cnt++;
							// 방문처리
							visitTmp[nextY][nextX] = true;
							q.add(new int[] { nextY, nextX });
						}
					}

					// 외곽과 닿아있거나 더 낮은 자리가 존재한다면 다음 땅 검사
					if (isOuter) {
						q.clear();
						for (int j2 = 0; j2 < row; j2++) {
							for (int k = 0; k < col; k++) {
								if (visitTmp[j2][k]) {
									visitTmp[j2][k] = false;
									visitPerma[j2][k] = true;
								}

							}
						}
						break;
					}

					// 방문한 땅(같은 높이)의 높이를 증가
					for (int j2 = 0; j2 < row; j2++) {
						for (int k = 0; k < col; k++) {
							if (visitTmp[j2][k]) {
								bd[j2][k] += (ceilHeight - fstLv);
								visitTmp[j2][k] = false;
								ans += (ceilHeight - fstLv);
								visitPerma[j2][k] = true;
							}
						}
					}
				}
			}
		}
		
		System.out.println(ans);
	}
}

---