백준 1113번 : 수영장 만들기

 문제

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

1113번: 수영장 만들기

1113 수영장 만들기

 

 구현 방법

한 번에 물의 양을 구하지 않고 한 층씩 해당 높이에서의 고일 수 있는 물을 구하여 더해주었습니다.

1. 값이 입력될 때 수영장의 최대 높이를 구해준다.
2. 높이를 1부터 수영장의 최대 높이만큼 탐색한다.
3. h층의 행, 열을 전부 훑어보며 h보다 낮은 층수가 있다면 방문처리 후 큐에 넣어준다.
4. 4방을 탐색하며 범위안에 들고 방문하지 않고 현재 층수보다 낮은 층수면 큐에 추가로 넣어준다.
5. 범위를 벗어나면 고일 수 없다는 뜻으로 flag를 false로 처리하여 확인을 한다. (* 범위를 벗어난다고 바로 return 하면 안됨)
6. 큐를 다 탐색했다면 flag가 true인지 false인지 확인한 후 카운트를 리턴해준다.

범위를 벗어나면 주변에 같이 탐색되는 애들도 같이 범위를 벗어나는거여서 고일 수 없습니다.

이걸 생각안하고 벗어나면 바로 리턴을 하여 틀렸습니다.

따라서 범위를 벗어난다고 바로 리턴 하지말고 따로 처리를 해줘야합니다.

 

 구현 코드

package BOJ.Gold;

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

public class BOJ1113_수영장만들기 {
	static int R, C, cnt, MAX, totalCnt;
	static boolean flag;
	static Queue<int[]> queue;
	static int[][] map, dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static boolean[][][] visit;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		visit = new boolean[R][C][10];
		MAX = Integer.MIN_VALUE;
		queue = new LinkedList<>();
		for (int r=0;r<R;r++) {
			String input = br.readLine();
			for (int c=0;c<C;c++) {
				map[r][c] = input.charAt(c)-'0';
				if (map[r][c]>MAX) MAX = map[r][c]; // 최대 높이 구하기
			}
		}
		System.out.println(bruteforce());
	}
	
	static int bruteforce() {
		for (int h=1;h<=MAX;h++) {
			for (int r=0;r<R;r++) {
				for (int c=0;c<C;c++) {
                	// 방문하지 않고 물이 고일 수 있다면 bfs 돌리기
					if (!visit[r][c][h] && map[r][c]<h) { 
						cnt = 1;
						queue.offer(new int[] {r, c});
						visit[r][c][h] = true;
						totalCnt += bfs(h);
					}
				}
			}
		}
		return totalCnt;
	}
	
	static int bfs(int h) {
		flag = true;
		while(!queue.isEmpty()) {
			int size = queue.size();
			for (int s=0;s<size;s++) {
				int[] now = queue.poll();
				for (int d=0;d<4;d++) {
					int nr = now[0]+dir[d][0];
					int nc = now[1]+dir[d][1];
					if (isIn(nr, nc) && !visit[nr][nc][h] && map[nr][nc]<h) {
						queue.offer(new int[] {nr, nc});
						visit[nr][nc][h] = true;
						cnt++;
					}
                    // 범위를 벗어난다면 물이 고일 수 없음
                    else if (!isIn(nr, nc)) flag = false; 
				}
			}
		}
		if (flag) return cnt; // 물이 고일 때만 cnt 리턴
		else return 0;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!