백준 2583번 영역 구하기(자바) - dfs, bfs

---

풀이 방법

1. 일단 map[][]을 만들고 주어진 직사각형 좌표를 이용해 색칠된 직사각형 부분을 map[][] = 1로 만들어준다.

2. bfs를 이용하여 상하좌우 칸을 탐색하여 칠해지지 않은 부분이 있다면 count를 올려가며 영역의 넓이를 구한다.

3. bfs를 부를 때마다 areaCount를 1씩 증가시켜 분리되는 영역의 개수를 구한다.

 

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

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int areaCount;
    static ArrayList<Integer> area;
    static int m;
    static int n;

    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        int 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 = x1; a < x2; a++) {
                for (int b = y1; b < y2; b++) {
                    map[b][a] = 1;   //b와 a 순서 바꿔줘야 함
                }
            }
        }

        area = new ArrayList<Integer>();
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(map[i][j] == 0 && !visited[i][j]) {
                    areaCount++;
                    bfs(i, j);
                }
            }
        }

        System.out.println(areaCount);
        Collections.sort(area);
        for (int i = 0; i < area.size(); i++) {
            if(area.size() != 0) System.out.print(area.get(i) + " ");
            else System.out.print(0);
        }

    }

    static void bfs(int x, int y) {
        Queue<Node> queue = new LinkedList<>();
        visited[x][y] = true;
        queue.add(new Node(x, y));
        int count = 0;
        while (!queue.isEmpty()) {
            count++;
            Node node = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    if (!visited[nx][ny] && map[nx][ny] == 0) {
                        visited[nx][ny] = true;
                        queue.add(new Node(nx, ny));
                    }
                }
            }
        }
        area.add(count);
    }
}

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