[백준] 2468번 안전 영역 (java, bfs, 시뮬레이션)

www.acmicpc.net/problem/2468

2468번: 안전 영역

추가 설명에 비에 모두 잠기지 않을 가능성이 있다고 했다. (비가 안오는 경우가 있다. 높이 모두 1인 곳의 기준)

최대 지역의 높이 = 비의 최대 강수량으로 놓고 모든 비의 높이에 따라서 bfs를 돌려준다.

 

비의 높이보다 낮은 곳은 모두 0으로 만든 후 여전히 양수인 (물에 잠기지 않은 곳)의 영역을 구해준다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class  Pos{
	int y,x;

	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class Main {
	static int n;
	static int[][] map;
	static int[] xpos= {0,0,1,-1};
	static int[] ypos= {1,-1,0,0};
	static int max_rain;
	static int answer;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		map=new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j]=sc.nextInt();
				max_rain=Math.max(max_rain, map[i][j]);
			}
		}
//		물에 안잠길 수도 있다 => 비의 높이가 0일수도 있다.
		for (int height = 0; height <=max_rain; height++) {
			bfs(height);
		}
		
		System.out.println(answer);
		
	}
	private static void bfs(int height) {
		boolean[][] vis=new boolean[n][n];
		
		int[][] copy=copiedMap(map);
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(copy[i][j]<=height) {
					copy[i][j]=0;//물에 침수됨
				}
			}
		}
		
		int cnt=0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(copy[i][j]!=0 && !vis[i][j]) {//침수안된 지역 찾기
					Queue<Pos> q=new LinkedList<>();
					q.add(new Pos(i,j));
					vis[i][j]=true;
					while(q.size()!=0) {
						Pos cur=q.poll();
						int y=cur.y;
						int x=cur.x;
						for (int k = 0; k < 4; k++) {
							int yy=y+ypos[k];
							int xx=x+xpos[k];
							if(xx<0 || yy<0 || xx>=n || yy>=n)continue;
							if(vis[yy][xx])continue;
							
							if(copy[yy][xx]>0) {//시작 높이와 같다면
								vis[yy][xx]=true;
								q.add(new Pos(yy,xx));
							}
						}
						
					}
					cnt++;
				}
			}
		}
		answer=Math.max(answer, cnt);
		
		
	}
	
	private static int[][] copiedMap(int[][] map){
		int[][] copy=new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				copy[i][j]=map[i][j];
			}
		}
		return copy;
	}
	
}