[백준 / Java] 2468: 안전 영역 (BFS)

난이도: Silver 1

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

 

 

 

'그 크기가 최대인 영역'

처음에는 이게 무슨 말인지 이해가 안 돼서 여러번 읽어봤다. 

도대체 어떻게 세어야 저게 5개가 되는거지...? 왼쪽 아래꺼만 세어도 7개인데..? 하면서 답답해 하다가

혹시나 나처럼 이해가 안 되는 사람이 있나 해서 질문 게시판을 뒤져 보았다.

 

 

고수님들이 답변을 해주신 것을 보고 드디어 이해를 하였다.

그리고 문제 텍스트를 작성한 사람을 약간 원망하였다.. 좀 이해되기 쉽게 써주지.. 하면서 ..ㅋㅎㅋㅋ

 

자 그러면 이제 이해했으니 문제를 풀어나가야겠다!

 

 

높이가 4 이하인 모든 지점이 물에 잠긴 경우,

분홍색: 물에 잠기는 지점

파란색: 물에 잠기지 않는 안전한 영역

 

"인접한 영역끼리 묶인 영역을 1개의 안전한 영역으로 정한다." 의 원칙에 따라,

파란색 영역의 묶음은 총 5개가 된다.

 

(티스토리 처음 써보는데 너무 불편하네.. 글자색도 곧바로 안바껴 아오.. 사람들이 많이 쓰는 사이트니까 참는다..)

 

물에 잠기지 않는 안전한 영역의 최대 개수를 찾아야 하므로,

높이가 0(비가 아예 오지 않는 경우)부터 최대 높이까지 모든 경우의 수를 따져봐야 한다. 

즉, 0부터 주어진 높이 값 중 최댓값까지 반복문을 돌려야 한다.

 

문제에서는 높이가 1부터 100까지 주어진다고 했지만, 사실 100까지 반복문을 돌릴 필요가 없다.

주어진 높이 값 중 최댓값까지만 반복문을 돌리면 모든 영역은 높이의 최댓값보다 작거나 같으므로 물에 잠기게 된다.

비가 안 오는 경우도 포함해야 하므로 높이는 반드시 1부터가 아닌 0부터 반복문을 돌려야 한다.

그렇지 않으면 69퍼에서 틀렸습니다. 가 뜬다... 나도 알고 싶지 않았다..

 

문제에서 주어진 2차원 배열은 matrix[N][N]에 저장하고,

bfs이므로 방문 배열이 있어야하므로 visited[N][N]를 만들어주고,

나는 count[N][N] 2차원 배열도 따로 만들어주었다.

matrix[i][j]가 물에 잠기는 높이보다 작거나 같다면, count[i][j]에 -1을 대입해서,

bfs가 그 영역은 탐색하지 않도록 하는 목적이다.

 

물에 잠기지 않는 안전한 영역은 각각 떨어져있기 때문에, bfs는 한 번만 돌리면 절대 안된다.

무조건 이중 for문을 사용해서 모든 구역을 탐색해야 한다.

해당 영역을 방문하지 않았거나 해당 영역이 물에 잠기지 않았다면 => if (!visited[i][j] || count[i][j] != -1)

해당 영역부터 bfs를 수행하면 된다. => bfs(i, j)

 

자, 그렇다면 이제 코드를 보자. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class P2468_안전영역 {
    static int[] dx = {1, 0, -1, 0};    // 아래, 위 이동
    static int[] dy = {0, 1, 0, -1};    // 오른쪽, 왼쪽 이동
    static int N;                        // 2차원 배열의 행과 열의 개수를 나타내는 수
    static int[][] matrix;                // 2차원 높이 배열
    static boolean[][] visited;            // 2차원 방문 배열
    static int[][] count;                // 2차원 각 높이에 따른 물에 잠기지 않는 안전한 영역의 개수 배열
    static int cnt;                        // 해당 영역이 몇 번째인지 카운트하는 변수
    static int maxCount;                // 물에 잠기지 않는 안전한 영역의 최대 개수
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        matrix = new int[N][N];
        int maxDepth = 0;        // 2차원 높이 배열에 있는 높이 중 최대 높이
        
        // 2차원 높이 배열 초기화
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
                maxDepth = Math.max(maxDepth, matrix[i][j]);    // 최대 높이 갱신
            }
        }
        
        // 높이가 0(비가 아예 오지 않는 경우)부터 최대 높이까지 모든 경우를 따져서
        // 물에 잠기지 않는 안전한 영역의 최대 개수 찾기
        for (int depth = 0; depth <= maxDepth; depth++) {
            visited = new boolean[N][N];    // 방문 배열 초기화
            count = new int[N][N];            // 물에 잠기지 않는 안전한 영역의 개수 배열 초기화
            cnt = 0;                        // 해당 영역이 몇 번째인지 카운트하는 변수 초기화
            sink(depth);                    // 각 높이 당 물에 잠기는 지점 표시
            maxCount = Math.max(maxCount, cnt);    // 물에 잠기지 않는 안전한 영역의 최대 개수 갱신
        }
        
        System.out.println(maxCount);        // 물에 잠기지 않는 안전한 영역의 최대 개수 출력
    }
    
    public static void sink(int depth) {
        // 각 높이 당 물에 잠기는 지점 표시
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 해당 높이가 물에 잠기는 높이보다 작거나 같으면, 물에 잠기므로
                if (matrix[i][j] <= depth) {
                    count[i][j] = -1;    // 해당 카운트 영역에 -1 삽입
                }
            }
        }
        
        // 영역은 모두 떨어져있기 때문에 모든 구역에서 bfs 수행
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 해당 영역을 방문하지 않았고, 해당 영역이 물에 잠기지 않았다면
                if (!visited[i][j] && count[i][j] != -1) {
                    cnt++;        // 해당 영역이 몇 번째인지 카운트하는 변수 1 증가
                    bfs(i, j);    // 해당 영역부터 bfs 수행
                }
            }
        }
    }
    
    public static void bfs(int a, int b) {
        Queue<int[]> queue = new LinkedList<>();    // bfs 수행을 위한 큐 생성
        queue.add(new int[] {a, b});    // 해당 영역부터 큐에 삽입
        visited[a][b] = true;            // 해당 영역 방문 체크
        count[a][b] = cnt;        // 해당 영역부터 시작이므로 몇 번째인지 카운트하는 변수 대입
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int[] now = queue.poll();        // 현재 위치
            
            for (int i = 0; i < 4; i++) {
                int x = now[0] + dx[i];        // 현재 좌표 기준으로 위, 아래 이동
                int y = now[1] + dy[i];        // 현재 좌표 기준으로 왼쪽, 오른쪽 이동
                
                // 인덱스 범위를 초과한다면 건너뛰기
                if (x < 0 || y < 0 || x >= N || y >= N) {
                    continue;
                }
                
                // 해당 영역을 방문했거나, 해당 영역이 물에 잠겼다면 건너뛰기
                if (visited[x][y] || count[x][y] == -1) {
                    continue;
                }
                
                queue.add(new int[] {x, y});    // 해당 영역 큐에 삽입
                visited[x][y] = true;            // 해당 영역 방문 체크
                count[x][y] = cnt;        // 해당 영역에 몇 번째인지 카운트하는 변수 대입
            }
        }
    }    
}