백준 1113번: 수영장 만들기

문제 설명

• https://www.acmicpc.net/problem/1113
• 웅덩이에 물을 얼마나 받을 수 있는지 구하는 문제입니다.

접근법

• BFS로 테두리를 구하는게 아니라 고여있는 물을 구했습니다.
  • 테두리는 대각선이 허용돼 훨씬 복잡합니다.
• 낮은 높이부터 순차대로 탐색했습니다.
  • 예제 2번의 경우 높이가 1인 곳 4군데를 4만큼의 물을 채운 뒤 해당 위치를 5로 바꾸고, 높이가 5인 곳을 BFS할 때 이들을 포함한 총 8군데에 9만큼의 물을 채우는 방식을 택했습니다.
  • 낮은 높이부터 탐색하기 위해 3중for문을 사용했습니다.
    (k = 높이, i = 행, j 열)
• 물을 채운 뒤 해당 위치에 한번 더 물을 넣을 수 있기 때문에(예제 2번) 방문을 취소합니다.
• 물이 넘치지 않을 때만 높이를 더하기 때문에 임시배열(candi)에 값을 담고 모든 BFS가 끝나고 물이 넘치지 않았을 때 물을 넣었습니다.
• BFS의 연결이 가장자리(0,N-1,M-1)와 연결되거나, 나보다 낮은 벽이 옆에 있다면 흘러넘칩니다.

정답

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

public class Main {
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	static int N,M,totalScore;
	public static void main(String[] args) throws IOException{
		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++) { // 낮은 숫자부터 BFS탐색을 진행
			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(totalScore);
		
	}
	
	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) {
        	// 물의 양을 더함
			totalScore += 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; // 물이 더 찰수 있기 때문에 방문을 취소함
			}
		}
	}

}