백준 - 2468

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

class Main {
    static int[][] area;
    static int N;
    static int[][] dir = {
            {1,0},{-1,0},{0,1},{0,-1}
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        area = new int[N][N];

        int maxH = 0;
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                area[i][j] = Integer.parseInt(st.nextToken());
                maxH = Math.max(area[i][j], maxH);
            }
        }
        int max = 0;
        for(int i = 0; i < maxH; i++){
            boolean[][] wet = isWet(i);
            boolean[][] visited = new boolean[N][N];
            int count = 0;
            for(int r = 0; r < N; r++){
                for(int c = 0; c < N; c++){
                    if(wet[r][c] && !visited[r][c]){
                        dfs(visited,wet,r,c);
                        count++;
                    }
                }
            }
            max = Math.max(max,count);
        }
        System.out.println(max);
    }
    static void dfs(boolean[][] visited, boolean[][] wet,int r, int c){
        visited[r][c] = true;

        for(int d = 0; d < 4; d++){
            int nr = r + dir[d][0];
            int nc = c + dir[d][1];

            if(nr >= 0 && nc >= 0 && nr < N && nc < N && !visited[nr][nc] && wet[nr][nc]){
                visited[nr][nc] = true;
                dfs(visited,wet,nr,nc);
            }
        }
    }
    static boolean[][] isWet(int i) {
        boolean[][] wet = new boolean[N][N];

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (area[r][c] > i) {
                    wet[r][c] = true;
                }
            }
        }
        return wet;
    }
}

풀이과정 및 리뷰

1. 입력값(지형의 높이)을 받을 int[][] area , 방문여부 저장할 boolean[][] visited , 침수 여부 저장할 boolean[][] wet 배열 선언

   → 이때, area를 제외한 visited / wet 2차원배열은 비의 높이(0~최대높이-1)가 바뀔때마다 초기화됨

2. dfs(boolean[][] visited, boolean[][] wet, int r, int c) 메서드를 이용해 비의 높이별 visited / wet 배열의 방문여부 / 침수여부를 업데이트함 + wet[r][c] && !visited[r][c] 조건을 충족하는 좌표 (r,c)의 4방향을 탐색함

   → 흐름

   1. 2차원배열 For문 안에서, 젖지 않았고 방문하지 않은 좌표를 발견하면 dfs 호출
   2. 함수 내부에서 4방향 탐색을 하면서, 주위 4방향에 젖지 않은 지역이 있을때마다 재귀호출
   3. 주위 4방향에 침수된 지역밖에 없다면 메서드가 종료되며 count가 올라감

리뷰

문제점 1. boolean[][] wet 배열은 사실 젖지 않은 지역이 true로 저장된다….헷갈리게 변수명을 설정함

문제점 2. 코드 길이가 너무 길다..그에 비해 실행시간은 짧은 점은 놀랍다.

아쉬운 점.

1. wet배열을 반대로 생각해 젖은 지역을 true로 설정했다면, 매 rain마다 배열을 초기화 할 필요 없이 재사용(값 덮어쓰기)가 가능했음
2. 비의 높이가 ‘비가 내리지 않는 경우도 있다’는 조건때문에, 0~ maxH-1까지 탐색했지만, 어느 로직을 적용해 최적의 비높이 사이에서만 For문을 반복하는 방법이 있을 것도 같다..(못찾음ㅎ)