[Java] 백준 1113번 : 수영장 만들기

문제

지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다.

16661
61116
16661

이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다.

자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수 할 수 있다.

땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 땅의 높이가 주어진다. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

3 5
16661
61116
16661

예제 출력 1

15

예제 입력 2

4 6
999999
955119
955119
999999

예제 출력 2

48

예제 입력 3

5 9
111111111
115111611
131516161
115111611
111111111

예제 출력 3

7

예제 입력 4

9 13
1111111111111
1555555555551
1511111111151
1511199911151
1511192911151
1511199911151
1511111111151
1555555555551
1111111111111

예제 출력 4

151

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, M, max=Integer.MIN_VALUE;
	private static int[][] graph;
	private static int[] dx = { -1, 1, 0, 0 };
	private static int[] dy = { 0, 0, -1, 1 };

	static class Point {
		int r, c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}

	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		graph = new int[N][M];

		for (int r = 0; r < N; r++) {
			String s=br.readLine();
			for (int c = 0; c < M; c++) {
				graph[r][c] = s.charAt(c)-'0';
				if(graph[r][c]>max) max=graph[r][c];	// 수영장의 최대 높이
			}
		}

		int result=0;
		for(int i=1;i<=max;i++) {	// 높이를 1부터 최대값까지 고려하며 각 높이보다 낮은 위치에 있는 물을 1씩 채워줌
			for(int r=1;r<N-1;r++) {
				for(int c=1;c<M-1;c++) {
					if(graph[r][c]<i) result+=bfs(i, r, c);	// (r, c)의 물이 i높이보다 낮으면 물을 채울 수 있는 영역인지 확인하러 감
				}
			}
		}
		System.out.println(result);
	}

	private static int bfs(int i, int r, int c) {
		Queue<Point> queue=new LinkedList<>();
		queue.add(new Point(r, c));
		graph[r][c]++;	// 물을 1만큼 채워줌
		int cnt=1;	// 물을 채운 영역의 개수 카운트
		
		boolean include=true;	// 경계와 맞닿아 있으면 물을 채울 수 없음
		while(!queue.isEmpty()) {
			Point p=queue.poll();
			
			for(int d=0;d<4;d++) {
				int nx=p.r+dx[d];
				int ny=p.c+dy[d];
				
				if(!isIn(nx, ny)) {	// 경계와 맞닿아 있는 경우
					include=false;
					continue;
				}
				if(graph[nx][ny]<i) {	// 경계와 만나지 않고, 높이 i보다 작은 값인 경우
					graph[nx][ny]++;	// 물을 1만큼 채워주고, 카운트 값 1 증가시킴
					cnt++;
					queue.add(new Point(nx, ny));
				}
			}
		}
		if(include) return cnt;	// 물을 채울 수 있는 경우 채운 양 리턴
		return 0;	// 물을 채울 수 없으면 0 리턴
	}

	private static boolean isIn(int r, int c) {
		return r >= 0 && r < N && c >= 0 && c < M;
	}
}

수영장 물을 높이의 최소값인 1부터 최댓값까지 1만큼씩 채워나가며 답을 찾아주었습니다. 수영장 경계와 물을 채울 수 있는 영역을 구분하는 것이 매우 어려웠던 문제였습니다. 완전탐색과 bfs를 함께 사용해주어 해결 가능했습니다.