입력을 받으며 지도의 최대 높이(maxHeight)를 찾는다.
0 ~ maxHeight 동안 안전 영역의 개수를 센다.
ch배열을 선언해 물에 잠김 or 방문한 영역임을 표시
발견하지 않은 지역이 있다면, 개수를 1 추가 후 DFS로 상하좌우 연결된 부분을 체크한다.
private static int countRegion(int height) {
int count = 0;
//물에 잠김 or 방문한 영역을 표시할 ch 배열
boolean[][] ch = new boolean[n][n];
//물에 잠긴 영역 표시
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(map[i][j]<=height)
ch[i][j] = true;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++){
//방문하지 않은 지역이 있다면
if(ch[i][j]==false){
count++; //개수 추가
DFS(i, j, ch); //연결된 부분 체크
}
}
return count;
}
private static void DFS(int r, int c, boolean[][] ch) {
//상하좌우로 탐색한다.
for(int i=0; i<4; i++){
int nr = r+ dr[i];
int nc = c+dc[i];
if(nr<0 || nr>=n || nc<0 || nc>=n) continue;
if(ch[nr][nc]==false){
ch[nr][nc]= true;
DFS(nr, nc, ch);
}
}
}
import java.util.*;
public class Main {
//상하좌우 탐색에 사용할 변위
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
static int n;
static int[][] map;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
map = new int[n][n];
int maxHeight = Integer.MIN_VALUE;
int answer = Integer.MIN_VALUE;
//지도를 입력 받으며 최대 높이 갱신
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = scanner.nextInt();
maxHeight = Math.max(maxHeight, map[i][j]);
}
}
//0 ~ maxHeight 동안 안전 영역의 개수를 센다.
for(int i=0; i<=maxHeight; i++){
//안전 영역의 최대 개수 갱신
answer = Math.max(countRegion(i), answer);
}
System.out.println(answer);
}
private static int countRegion(int height) {
int count = 0;
//물에 잠김 or 방문한 영역을 표시할 ch 배열
boolean[][] ch = new boolean[n][n];
//물에 잠긴 영역 표시
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(map[i][j]<=height)
ch[i][j] = true;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++){
//방문하지 않은 지역이 있다면
if(ch[i][j]==false){
count++; //개수 추가
DFS(i, j, ch); //연결된 부분 체크
}
}
return count;
}
private static void DFS(int r, int c, boolean[][] ch) {
//상하좌우로 탐색한다.
for(int i=0; i<4; i++){
int nr = r+ dr[i];
int nc = c+dc[i];
if(nr<0 || nr>=n || nc<0 || nc>=n) continue;
if(ch[nr][nc]==false){
ch[nr][nc]= true;
DFS(nr, nc, ch);
}
}
}
}