[백준 BOJ/Silver I] 2468번 : 안전 영역

 

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

2468번: 안전 영역

 

다 풀고나니 굉장히 복잡하게 푼거같다

내일 스터디에서 이야기 나눠보고 다시 풀어봐야겠음!!

 

 

**

 

1

boolean[] height = new boolean[101];

 

- 물에 잠기는 모든 경우의 수를 생각해봐야하기 때문에 존재하는 높이를 boolean 배열에 true로 표시해주었다

- 높이 범위가 100까지로 정해져있어서 크기 101인 배열로 선언해주었다 

 

 

2

	for (int i = 0; i < 101; i++) {
            if (height[i]) {
                check(i); // 잠길 수 있는 부분 확인해서 rain 배열 만들기

 

- 존재하는 높이면 이 높이까지 비가 내렸을 경우 어떻게 되는지 확인하기 위해 우선 check 함수로 들어가서 rain 배열을 만들어준다

 

    static void check(int x) {
        // x 이하인 부분은 물에 잠긴다

        rain = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] > x) rain[i][j] = 1; // 물에 안 잠기면 1로 표시
                else rain[i][j] = 0; // 물에 잠기면 0으로 표시
            }
        }
    }

 

 

- 해당 높이 이하는 물이 잠기는 것이고 이걸 0으로 표시해준다 잠기지 않는 부분은 1로 표시해준다

 

 

3

		for (int j = 0; j < N; j++ ) {
                    for (int k = 0; k < N; k++) {

                        if (rain[j][k] == 1) {
                            dq.addLast(new int[] {j, k});
                            rain[j][k] = 0;
                            bfs();
                            count++;
                        }
                    }
                }

 

- rain 배열을 만들고 다시 돌아와서 이 배열을 확인하다가 1을 만나면(=잠기지 않은 안전영역) 큐에 담아주고 bfs 함수로 들어간다

 

static void bfs() {
        while (!dq.isEmpty()) {
            int[] xy = dq.pollFirst();
            int x = xy[0];
            int y = xy[1];

            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) {
                    if (rain[nx][ny] == 1) {
                        dq.addLast(new int[] {nx, ny});
                        rain[nx][ny] = 0;
                    }
                }
            }
        }
    }

 

- 이어진 1들을 모두 확인하는 과정이다 (이어진 안전영역 확인)

- bfs를 돈 후 count 값을 하나씩 올려준다 (count는 영역의 개수를 세주는 용도)

answer = Math.max(answer, count);

 

- rain 배열 전체를 확인해주고나서는 현재 answer값과 비교해서 더 큰 값을 다시 answer에 저장해준다

(영역의 최대 개수가 답이 되기 때문에)

 

- 존재하는 높이마다 rain 배열을 만들어주고 영역 개수를 구해주고 최대를 갱신해주는것을 반복하면 최종 답이 나오게 돈다

- 아무 지역도 물에 잠기지 않을 경우에는 전체가 다 안전 영역이므로 답은 1이 된다 → 초기 answer 값을 1로 설정

 

 

 

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {

    static int N;
    static int[][] map;
    static int[][] rain; // 비온뒤
    static Deque<int[]> dq;
    static boolean[] height = new boolean[101];

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

    static int count;
    static int answer = 1;
    // 아무 지역도 잠기지 않는다면 안전영역은 전체(=1)라서 기본 answer를 1로 설정해두었다

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dq = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            String str[] = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                height[map[i][j]] = true;
            }
        }

        for (int i = 0; i < 101; i++) {
            if (height[i]) {
                check(i); // 잠길 수 있는 부분 확인해서 rain 배열 만들기
                //System.out.println(Arrays.deepToString(rain));
                count = 0;

                for (int j = 0; j < N; j++ ) {
                    for (int k = 0; k < N; k++) {

                        if (rain[j][k] == 1) {
                            dq.addLast(new int[] {j, k});
                            rain[j][k] = 0;
                            bfs();
                            count++;
                        }
                    }
                }
                answer = Math.max(answer, count);
            }
        }

        System.out.println(answer);
    }

    static void bfs() {
        while (!dq.isEmpty()) {
            int[] xy = dq.pollFirst();
            int x = xy[0];
            int y = xy[1];

            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) {
                    if (rain[nx][ny] == 1) {
                        dq.addLast(new int[] {nx, ny});
                        rain[nx][ny] = 0;
                    }
                }
            }
        }
    }

    static void check(int x) {
        // x 이하인 부분은 물에 잠긴다

        rain = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] > x) rain[i][j] = 1; // 물에 안 잠기면 1로 표시
                else rain[i][j] = 0; // 물에 잠기면 0으로 표시
            }
        }
    }
}