[백준 - 2468] 안전 영역 - Java

문제 설명

 

2468번: 안전 영역

 

접근 방법

해당 문제는 브루트포스, BFS, DFS를 활용하여 문제를 해결할 수 있었습니다. 우선 땅의 높이 정보가 주어지면 강수량 0(비가 안 온 경우) ~ 100(대지의 최대 높이는 100이닌까) 모든 경우에 대해 안전 영역을 구하도록 했습니다. 이때 대지가 물에 잠긴 것을 표시하기 위해 BFS를 활용하여 땅의 높이 정보인 int형 2차원 배열을 탐색하도록 했습니다. 이때 boolean 2차원 배열을 통해 특정 노드에서의 값이 강수량 미만이라면 해당 물이 잠겼다는 것을 별도로 boolean 값으로 나타냈습니다. 앞서 물이 잠긴 정보를 저장한 boolean 2차원 배열을 DFS를 활용하여 안전 영역의 개수를 구하도록 했습니다. 앞선 작업들을 반복하면서 안전 영역의 최대 개수를 구합니다.

 

 

전체 소스 코드

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

class Main {

    static int n, countOfSafeLands;
    static int[][] earth;
    static boolean[][] wateredEarth;
    static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

    static class Land {
        int x;
        int y;

        public Land(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        earth = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                earth[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = 0;

        for (int i = 0; i <= 100; i++) {
            countOfSafeLands = 0;
            wateredEarth = new boolean[n][n];
            water(i, new boolean[n][n]);
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (!wateredEarth[j][k]) {
                        count(j, k);
                        countOfSafeLands++;
                    }
                }
            }

            result = Math.max(result, countOfSafeLands);
        }

        System.out.println(result);
    }

    public static void water(int target, boolean[][] visited) {
        Queue<Land> queue = new LinkedList<>();
        queue.add(new Land(0, 0));
        if (earth[0][0] <= target) {
            wateredEarth[0][0] = true;
            visited[0][0] = true;
        }

        int nx, ny;

        while (!queue.isEmpty()) {

            Land land = queue.poll();

            for (int i = 0; i < 4; i++) {
                nx = land.x + dx[i];
                ny = land.y + dy[i];

                if (nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1 || visited[nx][ny]) {
                    continue;
                }

                visited[nx][ny] = true;

                if (earth[nx][ny] <= target) {
                    wateredEarth[nx][ny] = true;
                }

                queue.add(new Land(nx, ny));
            }
        }
    }

    public static void count(int x, int y) {
        wateredEarth[x][y] = true;

        if (x + 1 < n && !wateredEarth[x + 1][y]) {
            count(x + 1, y);
        }
        if (x - 1 > - 1 && !wateredEarth[x - 1][y]) {
            count(x - 1, y);
        }
        if (y + 1 < n && !wateredEarth[x][y + 1]) {
            count(x, y + 1);
        }
        if (y - 1 > - 1 && !wateredEarth[x][y - 1]) {
            count(x, y - 1);
        }
    }
}

 

 

참고자료

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