[Java] 2468 안전 영역

1. 문제 링크 및 문제

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

1-1 문제 요약

:높이별로 안전영역의 최대 개수

2. 해결 방법 생각해보자 ...

1. 0부터 최대 높이까지 Height 반복문을 돌림
2. 반복문 내용 :
   2-1. 0,0 ~ N,N 까지 방문하는데
   2-2. 현재 map의 값이 Height 보다 높으면
   2-3. 주변 영역도 함께 탐색하여 안전영역 체크
   2-4. 중복방문은 안되므로 visited 사용

3. 코드

import java.util.*;
import java.io.*;
import java.awt.Point;

public class Main {

    static int N;
    static int MaxSafeZone = Integer.MIN_VALUE;
    static int MaxHeight = Integer.MIN_VALUE;
    static int[][] map ;
    static boolean[][] visited;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static Queue<Point> que = new LinkedList<>();

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

        // 값 입력받기 -- >
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visited = new boolean[N][N];

		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
                MaxHeight = Math.max(MaxHeight,map[i][j]);
			}
		}
        // <-- 값 입력받기

        //높이 0 ~ MaxHeight 까지 반복
        for (int h=0;h<MaxHeight;h++){
            int SafeZone = 0;
            visited = new boolean[N][N];

            // 현재 높이보다 map 값이 높을 때, DFS 탐색 실행
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(map[i][j]>h && !visited[i][j]){
                        FindSafeZone(i,j,h);
                        SafeZone += 1;
                    }
                }
            }
            MaxSafeZone = Math.max(MaxSafeZone, SafeZone);
        }
        System.out.println(MaxSafeZone);
    }

    public static void FindSafeZone(int x, int y, int Height){
        visited[x][y] = true;

        for(int k=0;k<4;k++){
            int xx = x+dx[k];
            int yy = y+dy[k];
            if (xx<0 || xx>=N || yy<0 || yy>=N) continue;
            if (map[xx][yy] > Height && !visited[xx][yy]){
                FindSafeZone(xx, yy, Height);
            }
        }
    }

}