백준 2468번 : 안전영역(Java)

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

---

[풀이]

 

• 완전 탐색 유형의 문제입니다.
• 높이는 1이상 100이하의 정수이므로 for문으로 copyArr에 높이 이하일경우 0, 초과일 경우 1을 입력합니다.
• copyArr에 매번 넣을 때마다, 방문하지 않은 곳과 안전한 영역을 체크하며 solve() 메소드를 호출합니다.
• solve() 메소드는 dfs를 이용한 메소드입니다. 
  • 영역의 개수를 셀 때, solve() 메소드가 호출된 개수가 곧 영역의 개수입니다.
• answer의 변수를 1로 초기화하는 이유는, 문제에서 영역의 개수를 셀 때 안전하지 않은 영역을 1개로 세기 때문입니다.
• 오른쪽, 아래, 왼쪽, 위 네가지 방향을 모두 확인하며 재귀 방식으로 문제를 풀어나갑니다.

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n, count, answer;
    static int[][] arr, copyArr;
    static boolean[][] visited;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static void solve(int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < n) {
                if (!visited[nextX][nextY] && copyArr[nextX][nextY] == 1)
                    solve(nextX, nextY);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        answer = 1;

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

        for (int v = 1; v < 101; v++) {
            visited = new boolean[n][n];
            copyArr = new int[n][n];
            count = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (arr[i][j] <= v)
                        copyArr[i][j] = 0;
                    else
                        copyArr[i][j] = 1;
                }
            }

            for (int p = 0; p < n; p++) {
                for (int q = 0; q < n; q++) {
                    if (!visited[p][q] && copyArr[p][q] == 1) {
                        solve(p, q);
                        count += 1;
                    }
                }
            }
            answer = Math.max(answer, count);
        }
        System.out.println(answer);
    }
}