[Java] 백준 2468 : 안전영역

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

2468번: 안전 영역

 

---

 

- 비가 오지 않았을 때는 안전영역이 1이다. (하나의 덩어리로 보기 때문에) 

- 높이가 1인 경우부터 최고 높이까지 비에 잠겼을 경우 안전지대를 찾고 그 최대 값을 구한다. 

 

import java.util.*;


public class Main {
	
	static int N;
	static int [][] map;
	static boolean [][] check;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0,- 1, 0, 1};
	
	public static void main(String[] args){
		Scanner sc= new Scanner(System.in);
		N=sc.nextInt();
		map = new int[N][N];
		
		int max =0;
		for(int i=0;i<N;i++) {
			for(int j =0; j<N;j++) {
				map[i][j]=sc.nextInt();
				if(max<map[i][j])
					max = map[i][j];
			}
		}
		
		int res=0;
		for(int i=0; i<=max;i++) {
			int cnt =0;
			check = new boolean[N][N];
			for(int j=0;j<N;j++) {
				for(int k=0;k<N;k++) {
					if(map[j][k]>i&&!check[j][k]) {
						cnt++;
						dfs(j,k,i);
					}
				}
			}
			res=Math.max(cnt, res);
		}
		
		System.out.println(res);
	}// main()
	
	static void dfs(int x,int y,int height) {
		check[x][y]=true;
		
		for (int i = 0; i < 4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			//물에 잠겨 있거나 이미 확인한 곳이면,
			if(nx<0||ny<0||nx>=N||ny>=N||map[nx][ny]<=height||check[nx][ny])
				continue;

			dfs(nx,ny,height);
			
		}
	}//dfs()
	
}// class Main