[Silver I/JAVA] 2583 영역 구하기

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

 

 

조건

• M*N 모눈종이에 K개의 직사각형을 그림
• K개의 직사각형 내부를 제외한 나머지 부분을 구하는 것
• 분리된 영역 개수, 각 영역의 넓이를 출력(오름차순)

필요한 것

• 네 방향으로 움직이면서 탐색하기 위한 dx, dy 배열
• 영역 넓이 결과를 저장할 ArrayList (넓이가 얼마나 나올지 모르기 때문에 가변적인 ArrayList 사용)
• 영역 넓이를 저장할 cnt

풀이

• 여기서 M이 높이, N이 너비이다.
• x,y좌표값은 문제에서 설명하는 것과 다르더라도 그대로 2차원 배열로 나타내도 넓이는 같다.

• x, y 범위만큼 영역을 1로 채워줌
• 빈 영역을 DFS 탐색 

 

전체 코드

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

public class Main{
    static int[][] grid;
    static ArrayList<Integer> list = new ArrayList<>();
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int N,M;
    static int cnt;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        M = Integer.parseInt(str[0]); //M:높이
        N = Integer.parseInt(str[1]); //N:너비
        int K = Integer.parseInt(str[2]); //K:직사각형 개수
        
        //grid 초기화
        grid = new int[N][M];
        
        //좌표입력
        for(int i=0; i<K; i++){
            str = br.readLine().split(" ");
            int x1 = Integer.parseInt(str[0]);
            int y1 = Integer.parseInt(str[1]);
            int x2 = Integer.parseInt(str[2]);
            int y2 = Integer.parseInt(str[3]);
            
            for(int x=x1; x<x2; x++){
                for(int y=y1; y<y2; y++){
                    grid[x][y] = 1; //영역 1로 채우기
                }
            }
        }
        
        //DFS 탐색 (0,0)부터
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(grid[i][j]==0){
                    cnt = 0;
                    dfs(i, j);
                    list.add(cnt); //DFS탐색 끝난 뒤 count값 list에 결과저장
                }
            }
        }
        
        //출력 : 분리된 영역 개수
        System.out.println(list.size());
        
        //출력 : 각 영역 넓이 오름차순
        Collections.sort(list);
        for(Integer i : list){
            System.out.print(i + " ");
        }
    }
    
    //DFS
    private static void dfs(int x, int y){
        //영역이 채워져 있으면 cnt 증가
        grid[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<N && ny>=0 && ny<M){
                if(grid[nx][ny]==0){ //빈영역이면 탐색 계속
                    dfs(nx, ny);
                }
            }
        }
    }
}