[BOJ/JAVA] 2468 : 안전 영역

🌊 생각의 흐름

이 문제를 푼 과정을 정리해 보려고 한다.

1) 비의 양이 정해져있지 않다.
=> 모든 경우를 계산해서 최댓값을 구해야 한다.
비의 양 (즉, 잠기는 높이)이 1일 때 안전 영역, 2일 때 .. 를 다 구해서 저장할 배열이 필요하겠지

2) 안전 영역은 물에 잠기지 않는 지점들의 크기가 최대인 영역이다.
=> 메인 함수에서 dfs 호출시 cnt 값을 하나씩 늘려서 개수를 세자 그리고 한 바퀴 다 돌고나면 cnt랑 visited 초기화를 하자.

여기까지 하고 문제를 풀었지만 틀림

이유는 간단했다.
아무 지역도 물에 잠기지 않을 수 있다.

비의 양을 설정한 변수인 height를 1부터 설정했기 때문이다.

👉 정답 코드

import java.io.*;
import java.util.*;

public class _2468 {
    static int n,height,cnt;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        ArrayList<Integer> result = new ArrayList<>();

        n = Integer.parseInt(br.readLine());
        graph = new int[n][n];
        visited = new boolean[n][n];

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());

                if (graph[i][j] > max) max = graph[i][j];
            }
        }

        height = -1;
        
        while (true) {
            height++;
            cnt = 0;
            visited = new boolean[n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && graph[i][j] > height) {
                        cnt++;
                        dfs(i,j);
                    }
                }
            }
            result.add(cnt);
            if (height == max) break;
        }

        System.out.println(Collections.max(result));
    }

    static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                if (!visited[nx][ny] && graph[nx][ny] > height) {
                    dfs(nx,ny);
                }
            }
        }

    }
}

이렇게 사소하게 조건을 놓쳐서 틀리는 경우가 많은 거 같아서 다시 한번 일깨우기 위해 남긴다ㅜㅜ