백준 2468 - 안전 영역

문제

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

리뷰

BFS를 이용하여 간단하게 풀이할 수 있는 문제였다. 로직의 전개는 다음과 같다.

1. 입력을 받으며 높이를 Set에 삽입한다. 중복 없이 주어진 높이값을 저장할 수 있다.
   유의할 점은 아무 곳도 잠기지 않을 수 있기에 0 도 저장해주어야 한다는 점이다.
2. Set 의 값들을 순회하며 아래 연산을 수행한다.
   • visited 를 초기화 한다.
   • 잠긴 영역을 처리한다. (=해당 height 보다 낮은 값 가지는 위치들 visited , true 처리)
   • 안전 영역의 개수(=bfs 호출 횟수)를 도출한다.
   • 최대 안전 영역의 개수(maxSafeArea )를 갱신한다.

로직의 시간복잡도는 최대 $O(N^3)$으로 측정되나, $N$이 최대 100이기에 문제의
시간 제한 조건인 1초내에 충분히 수행된다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[][] area;
    static boolean[][] visited;
    static int[] px = {-1, 1, 0, 0};
    static int[] py = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Set<Integer> heights = new HashSet<>();

        N = parseInt(in.nextLine());
        area = new int[N][N];
        visited = new boolean[N][N];


        StringTokenizer st;
        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(in.nextLine());
            for (int x = 0; x < N; x++) {
                area[y][x] = parseInt(st.nextToken());
                heights.add(area[y][x]);
            }
        }

        heights.add(0);

        int maxSafeArea = 0;

        for (Integer height : heights) { // O(N)
            initVisited();
            areaShrinking(height);

            int safeArea = 0;

            for (int y = 0; y < visited.length; y++)
                for (int x = 0; x < visited[y].length; x++)
                    if (!visited[y][x]) {
                        bfs(x, y);
                        safeArea++;
                    }

            maxSafeArea = Math.max(maxSafeArea, safeArea);
        }

        System.out.println(maxSafeArea);
        in.close();
    }

    static void initVisited() { //O(N^2)
        for (int i = 0; i < visited.length; i++)
            Arrays.fill(visited[i], false);
    }

    static void areaShrinking(int height) { // O(N^2)
        for (int y = 0; y < visited.length; y++)
            for (int x = 0; x < visited[y].length; x++)
                if (area[y][x] <= height)
                    visited[y][x] = true;
    }


    static void bfs(int x, int y) { // O(N^2)
        visited[y][x] = true;
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(x, y));

        while (!queue.isEmpty()) {
            Node current = queue.poll();

            for (int i = 0; i < px.length; i++) {
                int nextX = current.x + px[i];
                int nextY = current.y + py[i];

                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N)
                    continue;

                if (!visited[nextY][nextX]) {
                    visited[nextY][nextX] = true;
                    queue.offer(new Node(nextX, nextY));
                }
            }
        }
    }

    static class Node {
        int x, y;

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

결과