백준, 안전 영역(2468, java)

문제 설명

각 지역의 높이가 주어지고 비가 내렸을 때 잠기지 않은 지역의 최대값을 구하는 문제이다.

 

부르트 포스로 전체 물의 양을 확인해서 구하고 물에 잠기지 않는 지역은 BFS로 풀면 된다. 다만, 전체 지역이 물에 잠기지 않을 수 있으니(지역의 모든 높이가 일정한 경우) 이 경우만 주의하면 된다.

 

문제 풀이

1. raining() 메소드로 잠긴 지역을 체크한다. 이때 비의 양의 범위는 주어진 높이의 최솟값부터 최댓값 사이이다. 나는 0부터 돌리지는 않았는데, 그 이유는 최솟값보다 작으면 어차피 잠기는 곳이 없기 때문이다. 

 

2. 잠긴 곳을 표시했으면 BFS를 돌려서 잠기지 않은 지역을 세주면 된다. 지금까지 풀어왔던 BFS 문제와 동일하게 해주면 된다.

 

3. 그리고 잠기지 않은 지역의 수가 현재의 answer보다 크다면 해당 값으로 answer를 갱신한다.

 

4. 그리고 답을 출력해주면 되는데, 이때 조심해야 할 것이 있다. 예를 들어서 N이 2라고 할 때 높이가 모두 4인 지역이 있다고 해보자. 그렇게 되면 min도 max도 전부 4일 테니, 우리가 푼 풀이로는 비의 양이 4만을 돌고 끝이 날 것이다. 이렇게 되면 나오는 결과는 0이 된다. 왜냐면 4가 전부 물에 잠겼으니 남은 지역이 없는 것이다.

 

이런 문제를 해결하기 위해서는 두 가지 방법이 있다. 하나는 min-1부터 반복문을 시작하는 것.  min-1일 3부터 반복문을 돌아 정답이 1이 될 것이다. 또 다른 하나는 만일 answer가 0일 경우 1을 출력하는 것. 나는 후자를 택했다.

 

문제 설명

코드

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

class Pair {
    int row;
    int col;

    Pair(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {

    public static int N,min, max;
    public static int[][] map;
    public static boolean[][] visit;
    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};

    public static void raining(int rain) {
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                if (map[i][j] <= rain) {
                    map[i][j] = -1;
                }
            }
        }
    }
    public static void bfs(int r, int c) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(r, c));

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            int cR = current.row;
            int cC = current.col;

            for (int i=0; i<4; i++) {
                int nR = cR + dR[i];
                int nC = cC + dC[i];

                if (nR >= 0 && nR < N && nC >= 0 && nC < N) {
                    if (map[nR][nC] != -1 && !visit[nR][nC]) {
                        visit[nR][nC] = true;
                        queue.add(new Pair(nR, nC));
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        map = new int[N][N];
        min = Integer.MAX_VALUE;
        max = 0;
        int count = 0;
        int answer = 0;

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

        for (int i=min; i<=max; i++) {
            raining(i);
            visit = new boolean[N][N];
            count = 0;
            for (int j=0; j<N; j++) {
                for (int k=0; k<N; k++) {
                    if (map[j][k] != -1 && !visit[j][k]) {
                        visit[j][k] = true;
                        bfs(j, k);
                        count++;
                    }
                }
            }
            answer = Math.max(answer, count);
        }

        if (answer == 0) {
            System.out.println(1);
        } else {
            System.out.println(answer);
        }

    }

}