백준 2468번 - 안전 영역(DFS)

---

위 문제에서

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7  를 예로 들면 

 

높이가 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 이하의 모든 지점이 물에 잠기는 경우의 수가 있고 그 중 안전한 영역의 최대 개수를 출력하는 내용이다

---

1. 높이가 0 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

모든 지역이 안전 구역이므로 안전한 영역의 개수는 1이 나온다

---

2. 높이가 1 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

모든 지역이 안전 구역이므로 안전한 영역의 개수는 1이 나온다

---

3. 높이가 2 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

안전한 영역의 개수는 1이 나온다

---

4. 높이가 3 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

안전한 영역의 개수는 4이 나온다

---

5. 높이가 4 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

안전한 영역의 개수는 5이 나온다

---

6. 높이가 5 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

안전한 영역의 개수는 5이 나온다

---

7. 높이가 6 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

안전한 영역의 개수는 4이 나온다

---

8. 높이가 7 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

안전한 영역의 개수는 2이 나온다

---

9. 높이가 8 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

안전한 영역의 개수는 1이 나온다

---

10. 높이가 9 이하인 모든 지점이 물에 잠겼다고 했을 때 

6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

안전한 영역의 개수는 0이 나온다

---

따라서 정리하면

0 → 1

1 → 1

2 → 1

3 → 4

4 → 5

5 → 5

6 → 4

7 → 2

8 → 1

9 → 0

중 최대값인 5가 출력되어야 한다.

 

▶코드

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

public class Main {
    static int N;
    static int cnt;
    static int range[][];
    static boolean visited[][];
    static int dx[] = {0, 0, -1, 1};
    static int dy[] = {-1, 1, 0, 0};
    static LinkedList<Integer> result;
    static int arr[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        range = new int[N][N];
        cnt = 1;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                range[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int max = range[0][0];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (max < range[i][j])
                    max = range[i][j];
            }
        }
        arr = new int[max+1];
        for (int a = 0; a <= max; a++) {
            visited = new boolean[N][N];
            result = new LinkedList<>();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (range[i][j] > a && !visited[i][j]) {
                        dfs(i, j, a);
                        result.add(cnt);
                        cnt = 1;
                    }
                }
            }
            arr[a] = result.size();
        }
        int answer = arr[0];
        for(int i=1;i<=max;i++){
            if(answer < arr[i])
                answer = arr[i];
        }
        System.out.println(answer);
    }
    public static void dfs(int x, int y, int a) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny] && range[nx][ny] > a) {
                dfs(nx, ny, a);
                cnt++;
            }
        }
    }
}