2468_안전 영역

사용 알고리즘: bfs

사용 언어: java

 

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 문제 이해가 안 돼서 애먹었던;;
 * 안전 영역? -> 영역 나누기의 그 영역으로 덩어리가 몇 개인지 세는 문제였따!
 * (덩어리 중 가장 큰 덩어리의 크기를 구하는 게 아니었다..)
 */
public class Main_2468_안전영역 {
    static int n;
    static int[][] map;
    static int cntMaxArea = 1;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,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];
        int maxH = 0;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                maxH = Math.max(maxH, map[i][j]);
            }
        }

        for(int precipitation = 0; precipitation<maxH; precipitation++) {
            int cntTmpArea = 0;
            boolean[][] visited = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(precipitation < map[i][j] && !visited[i][j]) {
                        cntTmpArea ++;
                        visited[i][j] = true;
                        bfs(i,j,visited, precipitation);
                    }
                }
            }

            cntMaxArea = Math.max(cntMaxArea, cntTmpArea);
        }

        System.out.println(cntMaxArea);

    }

    private static void bfs(int x, int y, boolean[][] visited, int precipitation) {
        Queue<Point> q = new ArrayDeque<>();
        q.offer(new Point(x,y));

        while (!q.isEmpty()) {
            Point p = q.poll();
            for (int d = 0; d < 4; d++) {
                int nx = p.x + dx[d];
                int ny = p.y + dy[d];

                if(nx>=0&&nx<n&&ny>=0&&ny<n) {
                    if (!visited[nx][ny]){
                        if(precipitation < map[nx][ny]) {
                            visited[nx][ny] = true;
                            q.offer(new Point(nx,ny));
                        }
                    }
                }
            }
        }
    }
}

 

코드에서도 써놨듯, 문제 설계 자체가 어렵다기 보다는 문제 이해가 어려웠다.

**각 영역 중 최대 크기를 구하는 게 아니라

**영역의 크기가 크든 작든 영역의 개수가 제일 많이 나올 때를 구하기!