[BOJ] 2468번: 안전 영역

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

2468번: 안전 영역

 

 

알고리즘 분류: DFS, BFS

 

public class Main {
	static Myscanner sc = new Myscanner();
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	static int safe[][],N,max,height;
	static boolean[][] visited = new boolean[N][N];
	public static void main(String[] args) {
		N = sc.nextInt();
		safe = new int[N][N];
		visited = new boolean[N][N]; 
		max =0;
		for(int r =0; r<N;r++)
		{
			for(int c =0 ;c<N;c++)
			{
				safe[r][c]=sc.nextInt();
				max = Math.max(max, safe[r][c]);
			}
		}

		int ans =1;
		for(height =1;height<=max;height++)
		{
			int cnt =0;

			for(int r = 0; r<N;r++)
			{
				for(int c =0; c<N;c++)
				{
					if(safe[r][c]>height && !visited[r][c]){
						cnt++;
						DFS(r,c);
					}
				}
			}
			ans = Math.max(ans, cnt);
			for(int i =0; i<N;i++){
				Arrays.fill(visited[i], false);
			}

		}
		out.println(ans);
        out.close();

	}
	private static void DFS(int r, int c) {

		if(r<0 || c<0 || r>=N || c>=N || safe[r][c]<=height || visited[r][c]) return;
		visited[r][c]=true;

		DFS(r-1,c);
		DFS(r+1,c);
		DFS(r,c-1);
		DFS(r,c+1);		

	}
}

 

DFS로 문제 풀이를 하였다.

 

1. 배열의 값을 초기화할 때 최대 높이(max)를 구해놓는다.

2. height (1 <=h <=max)까지 기준점을 잡고 dfs를 통해 안전 영역이 몇 개인지 구한다.

3. ans =1  (기본적으로 h=1이면 모든 지역이 안전 영역이 되기 때문에)로 초기화한 후 ans와 cnt의 max값을 비교하여 값을 지정한다.

4. visited 배열이 static 이기 때문에 false 값으로 초기화해준다.