백준 No.2583 영역 구하기- JAVA

문제

눈금의 간격이 1인 MxN크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 작사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5,N=7인 모눈 종이 위에 <그림1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

M,N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그릭 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오

 

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

 

 

 

풀이

visited 배열을 생성해서 하려했는데 굳이 필요가 없을 거 같아 다시 지우고 했다. 이건 가장 어려운게 사각형을 체크하는게 어렵던 거 같다. 사각형 체크는 preX, preY, posX, posY 이런식으로 받아서 진행하는데 여기서 중요한게 실제 2차원 배열은 preX가 [][x위치] 로 동작한다. 그니깐 결국 X,Y 좌표로 볼 때 X는 가로축이다. 세로축이 아니다 -> 이부분 떄문에 계속 이상한 값나옴 

결국 세로축이 아니고 가로축이기에 map[y][x] 이런식으로 직사각형이 그려져야 한다는 뜻이다. 이런 사각형이 그려지는 거 외에는 X,Y가 달라져도 크게 상관없음 

이런식으로 들어온다. 이렇게 체크를 1로 하면 탐색할 때 0인 곳만 탐색해서 하면 된다.

 

for(int i = preX; i< postX ; i++){
	for(int j = preY ; j < postY ; j++){
 		map[j][i] = 1;  // x는 가로축 y는 세로축   
    }
}

문제에서 함정이 있었는데 정렬이었다. 처음에 StringBuilder로 했는데 뭔가 이상해서 List로 바꿔서 정렬해줬다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {

    static int M,N, K;
    static int map[][];

    static int dx[] = {1,0,-1,0};
    static int dy[] = {0,1,0,-1};

    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());


        M = Integer.parseInt(st.nextToken());   //높이
        N = Integer.parseInt(st.nextToken());   //너비
        K = Integer.parseInt(st.nextToken());

        map = new int[M][N];


        for (int i = 0; i < K ; i++) {
            st = new StringTokenizer(br.readLine());

            int preX = Integer.parseInt(st.nextToken());
            int preY = Integer.parseInt(st.nextToken());
            int posX = Integer.parseInt(st.nextToken());
            int posY = Integer.parseInt(st.nextToken());

            for (int j = preX; j < posX ; j++) {	//바꿔도 상관없지만 xy축도 바꿔야함
                for (int k = preY; k < posY ; k++) {
                    map[k][j] = 1;
                }
            }
        }
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            for (int k = 0; k < N ; k++) {
                if(map[i][k] == 0){
                    count = 0;
                    dfs2(i,k);
                    list.add(count);
                }
            }
        }
        System.out.println(list.size());
        Collections.sort(list);
        for (Integer temp : list){
            System.out.print(temp + " ");
        }
    }


    static void dfs2(int x, int y){
        map[x][y] = 1;	//visited체크 대신 1로 체크함
        count++;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue;

            if(map[nx][ny] == 0) dfs2(nx,ny);
        }

    }
}