[java] 백준 2468 : 안전영역

문제

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

2468번: 안전 영역

 

 

 

package main;
import java.io.*;
import java.util.*;

public class Main {

	static boolean[][] visited;
	static int[][] arr;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int n;
	

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		
		arr = new int[n][n];
		
		int maxHeight = 0;
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
				maxHeight = Math.max(maxHeight, arr[i][j]);
		
			}
			
		}
		
		//안전영역 최댓값 탐색
		int max=0;
		for(int k=0; k< maxHeight+1; k++) {
			int cnt=0;
			visited = new boolean[n][n];
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					
					if(visited[i][j]==false && arr[i][j]> k) {
						cnt++;
						DFS(i,j,k);
					}
				}
				
			}
			max = Math.max(max, cnt);
		}
		
		System.out.println(max);
		
		
	}
	
	//안전지대 탐색
	static void DFS(int x, int y, int height)
	{
		visited[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) {
				if(visited[nx][ny]==false && arr[nx][ny]> height) {
					DFS(nx,ny,height);
				}
			}
		}
		
	}
}

visited가 되지 않고 height보다 큰 값이면

cnt(즉 안전영역 수)를 증가시키고 dfs로 height 보다 큰 값만 visited 한다. 그러면 안전영역만 visited 되어 다음 for문에서 visted==false인것만 탐색하여 안전 영역의 수를 탐색할 수 있게 된다.