영역 구하기 - 2583

문제

입력
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

출력
3
1 7 13

풀이

package Baekjoon;


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

//백준 - 2583 - 영역 구하기 - s1
public class ex2583 {
    static int n,m,k,cnt=0;
    static int[][] board;
    static ArrayList<Integer> arr;
    static int[] dx={0,1,0,-1};
    static int[] dy={-1,0,1,0};


    public static void DFS(int x, int y){
        board[x][y]=1;
        cnt++;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<m && ny>=0 && ny<n && board[nx][ny]==0){
                DFS(nx,ny);
            }
        }
    }

    public static void solution(int[][] board){
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j]==0){
                    cnt=0;
                    DFS(i,j);
                    arr.add(cnt);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        m=sc.nextInt();
        n=sc.nextInt();
        k=sc.nextInt();
        board = new int[m][n];

        for(int i=0; i<k; i++){
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();

            for(int a=y1; a<y2; a++){
                for(int b=x1; b<x2; b++){
                    board[a][b] = 1;
                }
            }
        }

        arr = new ArrayList<>();
        solution(board);
        System.out.println(arr.size());
        Collections.sort(arr);
        for(int x : arr){
            System.out.print(x + " ");
        }
    }
}

백준은 항상 느끼지만, 프로그래머스와 달리 입력받는게 제일 귀찮고 깐깐하다. ㅋㅋ 신경쓰자.
1. k개수 만큼 사각형인 부분을 board[a][b]에 1로 입력해둔다. 그러고 이제 나머지 영역을 구해야한다.
2. solution()함수로 board를 탐색하고 여기서 0이나오면 DFS()로 탐색시작!
3. 탐색한 부분은 다시 안돌아가기위해서 1로 체크해두고, 계속 탐색한다. DFS가 호출될때마다 한칸을 탐색하는 것이기 때문에 영역의 크기를 구할 cnt를 ++ 해준다. cnt 초기화에 유의하자!