백준 2583번 - 영역 구하기(DFS)

 

▶코드

import java.util.*;
import java.io.*;

public class Main {
    static int M, N, K;
    static int range[][];
    static boolean visited[][];
    static int dx[] = {0, 0, -1, 1};
    static int dy[] = {-1, 1, 0, 0};
    static int cnt;
    static LinkedList<Integer> result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        cnt = 1;
        range = new int[M][N];
        visited = new boolean[M][N];
        result = new LinkedList<>();

        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());
            int max_x = Math.max(x1, x2);
            int min_x = Math.min(x1, x2);
            int max_y = Math.max(y1, y2);
            int min_y = Math.min(y1, y2);
            for (int j = min_x; j < max_x; j++) {
                for (int z = min_y; z < max_y; z++) {
                    if (range[z][j] != 1)
                        range[z][j] = 1;
                }
            }
        }
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (range[i][j] == 0 && !visited[i][j]) {
                    dfs(i, j);
                    result.add(cnt);
                    cnt = 1;
                }
            }
        }
        System.out.println(result.size());
        Collections.sort(result);
        for(int val:result)
            System.out.print(val+" ");
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx >= 0 && ny >= 0 && nx < M && ny < N && !visited[nx][ny] && range[nx][ny] == 0) {
                dfs(nx, ny);
                cnt++;
            }
        }
    }
}