[백준] 2468번 안전영역

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

2468번: 안전 영역

목표 : 2차원 배열에서 높이 정보가 주어졌을 때, 모든 경우를 다 조사해 물에 잠기지 않는 안전한 영역(위,아래,오른쪽,왼쪽으로 인접한 영역)의 최대 개수를 구하기 DFS 활용 높이는 1이상 100이하의 정수이기 때문에 가장 바깥의 for문을 작성 count 변수를 통해 안전한 영역 세기 count 변수가 max 변수보다 크면 max에 대입 max 변수는 답 주의할 부분은 아무 지역도 물에 잠기지 않을 수 있기 때문에 max 변수를 1로 초기화해주어야한다

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[][] map, dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
	static boolean[][] visited;
	static int N,count = 0,max =1;
	

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		map = new int[N][N];
		visited = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		
		for (int k = 1; k <= 100; k++) {//높이 1부터 100까지 잠기는 지 
			count = 0;//count 초기화
			
			for (int i = 0; i < N; i++) {//맵 한번 돌 때
				for (int j = 0; j < N; j++) {
					
					if(map[i][j]>k && !visited[i][j]) {
						DFS(i, j, k); //dfs 
						count++;
					}
				}	
			}
			visited = new boolean[N][N];//방문 초기화
			if(max<count) {
				max = count;
			}			
		}
		
	
		System.out.println(max);
	
	}// end of main

	public static void DFS(int x, int y,int k) {
	
		visited[x][y] = true;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			
			// 다음 좌표가 범위 안에 있고 다음 좌표가 k보다 크고 방문처리가 안된 부분을 다시 dfs
			if(isInside(nx,ny) && map[nx][ny] > k && !visited[nx][ny]) {
				DFS(nx,ny,k);
			}
		}
		
	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < N;
	}
}// end of class