[백준 2468] 안전 영역 - 자바(java)

 

 

이 문제를 이해해보면 

N * N 의 그래프 속에 높이가 정해져 있는데 그 높이가 서서히 차오르면서 섬의 물이 찬다고 생각했을 때 

상하좌우로 움직일 수 없는 섬의 개수가 최대로 있을 때에는 몇개가 있는가?

 

그러면 일단 물의 최대 높이는 섬의 최대높이를 넘길 수 없으니 섬의 최대 높이를 구하고

for문을 돌리며 BFS 또는 DFS를 사용해 동떨어져 있는 섬의 개수를 구해보면 되겠다.

 

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int N;
    static int[][] graph;
    static boolean[][] isVisit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int maxAns = 0;
        int max = 0;
        graph = new int[N][N];

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

        for (int i = 0; i < max; i++) {
            int ans = 0;
            isVisit = new boolean[N][N];
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    if (!isVisit[j][k] && graph[j][k] > i) {
                        ans++;
                        DFS(j, k, i);
                        //BFS(j,k,i);
                    }
                }
            }
            maxAns = Math.max(maxAns, ans);
        }

        System.out.println(maxAns);
    }

    public static void BFS(int x, int y,int water) {
        Queue<int[]> queue = new ArrayDeque<>();

        queue.add(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if(isVisit[nx][ny]) continue;
                if(graph[nx][ny] <= water) continue;
                queue.add(new int[]{nx, ny});
                isVisit[nx][ny] = true;
            }
        }
    }

    public static void DFS(int x, int y, int water) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(isVisit[nx][ny]) continue;
            if(graph[nx][ny] <= water) continue;
            isVisit[nx][ny] = true;
            DFS(nx, ny, water);
        }
    }
}

 

 

max를 통해 물의 최대 높이를 구하고

3중 for문을 돌리며 BFS 나 DFS가 새로운 값을 찾게 되면 ans를 늘리면서, 최댓값을 maxAns를 통해 받는다.

 

 

위에 것이 DFS로 푼 것이고

아래에 있는 것이 BFS로 푼 답인데

 

메모리 차이가 많이 난다. 

 

큐에 인접한 노드들을 다 집어넣기 때문에 추가 메모리가 드는 것인데, 이렇게 적은 양을 사용할 때는 DFS가 메모리적으로나 시간적으로도 유리하다.
하지만, 만약 검사해야할 양이 많아질 경우 DFS에서는 스택 오버플로우가 발생할 수도 있기 때문에 조심해야한다.