백준 2583. 영역 구하기 :: 돼지개발자

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

"BFS"

영역을 나 누 자 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static int m,n,k;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Integer> q = new LinkedList<>();
    static List<Integer> list = new ArrayList<>();
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static StringBuilder sb = new StringBuilder();
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        map = new int[m][n];
        visited = new boolean[m][n];
        
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            
            for (int a = m-y2 ; a <m-y1 ; a++) {
                for (int b = x1; b < x2 ; b++) {
                    map[a][b] = 1;
                }
            }
        }
        
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(map[i][j] == 1 || visited[i][j]) continue;
                
                visited[i][j] = true;
                q.add(i);
                q.add(j);
                count++;
                int size = 0;
                
                while(!q.isEmpty()) {
                    
                    int x = q.poll();
                    int y = q.poll();
                    size++;
                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        
                        if(nx < 0 || nx >= m || ny < 0 || ny >= n ||
                                visited[nx][ny] || map[nx][ny] == 1)
                            continue;
                        
                        visited[nx][ny] = true;
                        q.add(nx);
                        q.add(ny);
                    }
                }
                list.add(size);
            }
        }
        
        Collections.sort(list);
        
        for(int size : list) {
            sb.append(size+" ");
        }
        System.out.println(count);
        System.out.println(sb.toString());
    }
}