백준 2583번 영역구하기

문제 링크 : https://www.acmicpc.net/problem/2583

1. 배열크기 입력받고, 사각형갯수 입력받고

2. 배열에 사각형부분 표시해준 후에

3. 그래프 탐색알고리즘을 사용하여 사각형 이외영역의 갯수와 크기를 구하여 출력하는 문제였다

그래프탐색엔 dfs를 사용하였는데 bfs를 사용하여도 결과는 같다

이문제는 원본 배열을 수정하여도 문제푸는데 지장이 없길래

visited배열을 따로 두지않고 배열 하나에 사각형도 표시하고 방문한 지점도 표시하였다.

아래는 소스코드이다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
 
public class Main {
    static int m, n, count;
    static int[][] map;
    static int[] dx = { 0, 0, 1, -1 };
    static int[] dy = { 1, -1, 0, 0 };
    
    public static void main(String[] args) {
        
        int k;
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> ar = new ArrayList<Integer>();
        
        m = sc.nextInt();
        n = sc.nextInt();
        k = sc.nextInt();
        
        map = new int[m][n];
        
        for(int i=0; i<k; i++) {
            int sx = sc.nextInt();
            int sy = sc.nextInt();
            int ex = sc.nextInt();
            int ey = sc.nextInt();
            
            for(int j=sy; j<ey; j++) {
                for(int l=sx; l<ex; l++) {
                    map[j][l] = 1;
                }
            }
        }
        
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(map[i][j]==0) {
                    count = 0;
                    dfs(i, j);
                    ar.add(count);
                }
            }
        }
        
        Collections.sort(ar);
        System.out.println(ar.size());
        
        for(int i=0; i<ar.size(); i++) {
            System.out.print(ar.get(i) + " ");
        }
        
    }
    
    static public void dfs (int y, int x) {
        map[y][x] = 1;
        count++;
        
        for(int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny<0 || nx<0 || ny>=m || nx>=n) continue;
            if(map[ny][nx]==1) continue;
            
            dfs(ny, nx);
        }
    }
}