[JAVA] [BOJ] 2468. 안전 영역

장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 

처음에 그 높이만 물에 잠기는 줄 알고 많이 틀렸었다. 문제를 잘 읽도록 하자...

( 오랜만에 알고리즘 하니까 재미는 있지만 어렵네요 ㅠ )

 

1. 생각해보면 비가 내리지 않았을 경우? 혹은 최소 높이보다 비가 작게 내렸을 경우?

   안전 영역의 최소 값은 1이 된다. ( Key point)

( 내 생각에는 문제의 오류라고 생각한다. 최소 높이가 1이라면 비가 내리지 않았다가 된다. )

( 이 생각 때문에 몇번 틀렸다. )

 

2. 비는 최소 높이 부터 최고 높이의 - 1 까지만 내리는 것을 확인하면 된다. 

   ( 최고 높이 이상으로 내릴 경우 어차피 안전영역은 0 이다. 최소 안전 영역이 1이 되는 것을 위배한다. )

 

3. 비가 내려 침수 된 부분을 체크 해주고 나머지 부분으로 부터 bfs를 퍼트려 퍼트린 부분의 갯수를 세면 된다.

   ( 이 부분의 경우 bfs를 퍼트릴 때마다 map에 표시해주는 부분을 다르게 적어 적힌 값의 최대값을 체크 해 주었다. )

 

( 참고 ) 여기서 큐에 클래스가 아닌 Integer 값을 넣은 이유는

Integer/map.length를 하면 좌표의 i값이

integer%map.length를 하면 좌표의 j 값이 나오기에 큐에 Integer를 넣었다.

맵에 적어주는 부분에 대해서는 코드를 보면 알겠지만 cnt를 따로 처리해주었다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main2468 {
	static int maxSafeZone;	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		maxSafeZone = 1;
		int N = Integer.parseInt(br.readLine());
		int[][] map = new int[N][N];
		
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		String[] input = null;
		for(int i=0; i<N; ++i) {
			input = br.readLine().split(" ");
			for(int j=0; j<N; ++j) {
				map[i][j] = Integer.parseInt(input[j]);
				if(max < map[i][j]) {
					max = map[i][j];
				}
				if(min > map[i][j]) {
					min = map[i][j];
				}
			}
		}
		for(int i=min; i<max; ++i) {
			bfs(flooding(map, new int[N][N], i));
		}
		bw.write(""+maxSafeZone);
		bw.close();
		br.close();
	}
	
	static int[][] flooding(int[][] map, int[][] temp, int value) {
		for(int i=0; i<map.length; ++i) {
			for(int j=0; j<map[i].length; ++j) {
				if(map[i][j] <= value) {
					temp[i][j] = -1;
				}
			}
		}
		return temp;
	}
	
	static void bfs(int[][] map) {
		int[] dx = {0, 0, 1, -1};
		int[] dy = {1, -1, 0, 0};
		int N = map.length;
		int[][] tempMap = new int[N][N];
		int x = 0;
		int y = 0;
		int ni = 0;
		int nj = 0;
		int value = 0;
		int cnt = 0;
		
		Queue<Integer> q = new LinkedList<Integer>();
		for(int i=0; i<N; ++i) {
			for(int j=0; j<N; ++j) {
				if(map[i][j] != -1 && tempMap[i][j] == 0) {
					cnt++;
					q.offer(i*N+j);
					while(!q.isEmpty()) {
						value = q.poll();
						x = value/N;
						y = value%N;
						tempMap[x][y] = cnt;
						for(int l=0; l<4; ++l) {
							ni = x + dx[l];
							nj = y + dy[l];
							if(ni < 0 || nj < 0 || ni > N -1 || nj > N -1 ) continue;
							if(tempMap[ni][nj] == 0 && map[ni][nj] != -1) {								
								tempMap[ni][nj] = cnt;
								q.offer(ni*N+nj);
							}
							
						}
					}
				}
			}
		}
		int max = 0;
		for(int i=0; i<N; ++i) {
			for(int j=0; j<N; ++j) {
				if(tempMap[i][j] > max) {
					max = tempMap[i][j];
				}
			}
		}
		if(max > maxSafeZone) {
			maxSafeZone = max;
		}
		
		
	}

}