안전영역

📍 문제 설명

 

💡 접근

다 잠기지 않는 경우부터 다 잠기는 경우까지 해당 높이에 따라 안전 영역 계산해주면 되는 문제였다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer,cnt, max;
    static int[][] board, dis, clone;
    static boolean[][] visited;
    static int[] ch,pm, combi;
    static boolean flag = true;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt(); //지역 정보
        int h = 0;
        board = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = kb.nextInt();
                if(board[i][j] > h) h = board[i][j];
            }
        }


        //높이가 1인 지점이 물에 잠겼을 때 ~ 최댓값인 지점이 물에 잠겼을 때의 안전영역갯수를 구한다.
        //높이가 0이라 다 안잠기는 경우 - 안전영역은 1
        //높이가 최댓값이라 다 잠기는 경우 - 안전영역은 0
        for(int i = 0; i <= h; i++) {
            visited = new boolean[n][n];
            answer = 0;
            T.solution(0,0, i);
            max = Math.max(answer, max);
        }
        System.out.println(max);
    }


    static void solution(int x, int y, int maxh) {
        //maxh보다 높은 지점을 만나면 안전영역의 갯수를 추가해주고 해당 영역은 true으로 바꾸자.
        for(int i = x; i < n; i++) {
            for(int j = y; j < n; j++) {
                //방문하지 않았고 비의 높이보다 커야 잠기지 않음
                if(!visited[i][j] && board[i][j] > maxh) {
                    answer++;
                    visited[i][j] = true;
                    //상하좌우 확인해서 모두 방문처리
                    DFS(i, j, maxh);
                }
            }
        }
    }

    private static void DFS(int x, int y, int maxh) {
        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 && board[nx][ny] > maxh && !visited[nx][ny]) {
                visited[nx][ny] = true;
                DFS(nx, ny, maxh);
            }
        }
    }
}