[백준 코딩테스트] 2468번 안전 영역

내 풀이

DFS 알고리즘을 사용해 풀이하면 금방 쉽게 풀 수 있는 문제였다.
이때 물에 잠기지 않은 안전한 영역의 최대 개수를 구해야하는데, 위/아래, 왼쪽/오른쪽 인접한 영역만 고려를 하면된다.

이때 물에 잠기는 높이가 1 이하라고 하면 입력이 위의 사진과 같을 때 잠기지 않는 영역이 25라고 생각할 수 있겠지만 덩어리로 보기에 한 개라고 봐야 한다.

위의 그림과 같이 각각 1~max까지 순회하며 안전한 영역의 최대 개수를 구해야 한다.

우리는 방문한 노드(visited[])인지 구분해야 하며, 또 각 입력에서 최대 높이(max)를 갱신해서 불필요한 반복문의 횟수를 줄여야 한다. 또한, 인접한 영역에서의 잠기지 않는 영역을 알아내기 위해 dx[], dy[] 배열을 사용한다.

내 코드

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

public class Main {
    static int n;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};

    static void dfs(int x, int y, int h){
        visited[x][y] = true;
        for(int i=0; i<4; i++){
            int currX = x + dx[i];
            int currY = y + dy[i];

            if(currX>=0 && currX<n && currY>=0 && currY<n && !visited[currX][currY] && board[currX][currY]>h){ // 방문한 노드가 아니며, 물에 잠기지 않아야함
                dfs(currX, currY, h);
            }

            
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        visited = new boolean[n][n];

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

        int res=0;
        for(int i=0; i<=max; i++){ // 높이
            for(int j=0; j<n; j++){
                Arrays.fill(visited[j], false); // 매번 FALSE로 초기화
            }
            
            int cnt=0;
            for(int j=0; j<n; j++){
                for(int k=0; k<n; k++){
                    if(board[j][k]>i && !visited[j][k]){
                        cnt++;
                        dfs(j, k, i);
                    }
                }
            }

            res = Math.max(cnt, res);
        }

        System.out.println(res);
    }   
}