[알고리즘] 백준 2468 안전영역 -BFS- 자바

 

 

www.acmicpc.net/problem/2468

2468번: 안전 영역

 

백준 그래프 유형분류에서 푼 안전영역이라는 문제입니다. ㅎㅎ

 

지역마다 높이가 다른데 해당 높이보다 같거나 큰 비가 오면 지역이 물에 잠기게 됩니다.

모든 비오는 경우의 수에서 물에 안잠긴 지역들의 구역이 최대일때 몇 구역인지 구하는 기본적인 BFS 유형의 문제였습니다.

 

비에와서 잠긴 부분을 벽(isUnderWatered)라고 생각하고 풀면 됩니다.

풀이는 주석으로 충분하며 다음과 같습니다.

 

[Java]

import java.util.*;

class Main {
    private static int N;
    private static int[][] map;
    private static boolean[][] isUnderWatered; //물에 잠겼는지
    private static int answer = 0;
    private static int count = 0;
    private static List<Integer> heightList = new ArrayList<>(); //물 높이 경우의 수 리스트
    private static int[] dr = new int[]{-1, 0, 1, 0};
    private static int[] dc = new int[]{0, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                map[r][c] = sc.nextInt();
                if (!heightList.contains(map[r][c])) heightList.add(map[r][c]); 
            }
        }
        heightList.add(0); //높이 0인 경우의 수 추가(아무지역 안 잠긴 경우)
        Collections.sort(heightList);
        for (int height : heightList) {
            // 0. 초기화
            isUnderWatered = new boolean[N][N];
            count = 0;
            // 1. 물잠기기 세팅
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (map[r][c] <= height) { // 물 잠긴 곳
                        isUnderWatered[r][c] = true;
                    }
                }
            }
            // 2. 구역 탐색
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!isUnderWatered[i][j]) bfs(i, j);
                }
            }
            //최고 구역개수 갱신(답)
            answer = Math.max(answer, count);
        }
        System.out.println(answer);
    }

    private static void bfs(int _r, int _c) {
        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(new Point(_r, _c));
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int r = point.r;
            int c = point.c;
            for (int i = 0; i < 4; i++) {
                int r2 = r + dr[i];
                int c2 = c + dc[i];
                if ((r2 >= 0 && c2 >= 0 && r2 < N && c2 < N) && !isUnderWatered[r2][c2]) {
                    isUnderWatered[r2][c2] = true;
                    queue.offer(new Point(r2, c2));
                }
            }
        }
        count++; //한 구역 탐색완료
    }

    private static class Point {
        int r;
        int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!