[백준] 2468 문제 - 안전영역(Java) 문제 해결 방법과 풀이코드

이 문제를 이해하는데 쫌 시간이 오래 걸렸다. 간단하게 설명하면 각 칸마다 높이가 있고, 물이 0부터 차 올랐을 때 가장 큰 안전영역 개수를 구하면 된다. 물이 4만큼 차 올랐을 때 안전영역은 아래와 같이 구해진다.

 

 

 

만약에 물이 안차오르면 안전영역은 1이다. 그래서 각 칸의 높이가 전부 1이면 답은 1이다. 물의 최대 높이는 지역의 최대 높이이다. 그래서 물의 높이는 0부터 지역의 가장 큰 수만큼 돌려주면 된다.

물의 높이 0도 신경 써야 하는 이유는 메모에 "아무 지역도 물에 잠기지 않을 수도 있다." 는 조건이 있기 때문이다.

 

[전체 풀이 코드]

package baekjoon.classfication.dfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//https://www.acmicpc.net/problem/2468
public class 안전영역_2468 {

    static int N;
    static int maxHeight;
    static int[][] map;
    static boolean[][] isVisited;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    static int maxSafeArea = 0;

    private static void input() throws Exception {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());

       N = Integer.parseInt(st.nextToken());
       map = new int[N][N];
       isVisited = new boolean[N][N];

       for (int i = 0; i < N; i++) {
          st = new StringTokenizer(br.readLine());
          for (int j = 0; j < N; j++) {
             int height = Integer.parseInt(st.nextToken());
             maxHeight = Math.max(maxHeight, height);
             map[i][j] = height;
          }
       }
    }

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

       solve();

       print();
    }

    private static void print() {
       System.out.println(maxSafeArea);
    }

    private static void solve() {
       if (maxHeight == 1) {
          maxSafeArea = 1;
          return;
       }

       for (int k = 1; k < maxHeight; k++) {
          int safeArea = 0;

          for (int i = 0; i < N; i++) {
             for (int j = 0; j < N; j++) {
                if (map[i][j] > k && !isVisited[i][j]) {
                   isVisited[i][j] = true;

                   safeArea++;
                   dfs(i, j, k);
                }
             }
          }
          maxSafeArea = Math.max(safeArea, maxSafeArea);
          resetIsVisited();
       }
    }

    private static void dfs(int y, int x, int maxHeight) {
       for (int i = 0; i < 4; i++) {
          int qy = y + dy[i];
          int qx = x + dx[i];

          if (qy >= 0 && qy < N && qx >= 0 && qx < N && !isVisited[qy][qx] && map[qy][qx] > maxHeight) {
             isVisited[qy][qx] = true;
             dfs(qy, qx, maxHeight);
          }
       }
    }

    private static void resetIsVisited() {
       for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
             isVisited[i][j] = false;
          }
       }
    }
}