이것저것 개발 블로그

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

풀이)

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

public class Main_BJ_2583_영역구하기 {
    static int n, m, sum;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static ArrayList<Integer> areas = new ArrayList<>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new boolean[n][m];
        for(int i=0; i<k; i++){
            st = new StringTokenizer(br.readLine());
            int ly = Integer.parseInt(st.nextToken());
            int lx = Integer.parseInt(st.nextToken());
            int ry = Integer.parseInt(st.nextToken());
            int rx = Integer.parseInt(st.nextToken());
            for(int x=lx; x<rx; x++){
                for(int y=ly; y<ry; y++){
                    visited[x][y] = true;
                    map[x][y]++;
                }
            }
        }//k

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(!visited[i][j]) {
                    int area = bfs(i, j);
                    sum++;
                    areas.add(area);
                }
            }
        }
        System.out.println(sum);
        Collections.sort(areas);
        for(int i=0; i<areas.size(); i++)
            System.out.print(areas.get(i)+" ");

    }//main
    private static int bfs(int x, int y){
        int area = 0;
        visited[x][y] = true;
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {x, y});

        while(!q.isEmpty()){
            int[] cur = q.poll();
            area++;
            for(int i=0; i<4; i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(check(nx, ny) && !visited[nx][ny]){
                    q.offer(new int[] {nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }//while
        return area;
    }//bfs
    private static boolean check(int x, int y) {
        if(x<0 || y<0 || x>=n || y>=m)
            return false;
        return true;
    }
}

만약, 완탐과 dfs, bfs 문제를 많이 풀어봤다면 문제 자체는 어렵지 않다!

다만,,,, 조건을 좀 많이 주의해야해서...ㅎ

처음에는 너무 단순히 아래를 0,0 을 잡았다해서 위 아래만 바뀐거라 괜찮아~~ 했는데,,

1. 행과 열이 바뀌어 있는 문제입니다....

2. 최소 좌표와 최대 좌표가 있는데, 최대 좌표를 -1 만큼 탐색하면 일반 탐색과 다를 것이 없습니다.

나머지는 입력을 받으면서 직사각형을 그린 영역을 visited 처리해주고,

전체 완탐을 하면서 visited 안 한 곳을 찾아주면 된다!

bfs를 통해 visited가 아닌 곳의 영역 수를 구하면 되고, 이는 bfs의 return값을 이용하여 영역을 저장해준다.

그리고 areas라는 ArrayList 배열을 정렬하면 끝!!