[백준 BOJ 2583번] 영역 구하기 (C / C++ ) [BFS, 그래프이론]

2583번: 영역 구하기 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	128MB	21223	11819	9381	56.686%

 

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

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

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

예제 입력 1

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

예제 출력 1

3
1 7 13

풀이

배열로 생각해보면 좌표값이 뒤집혀있고 배열 칸이 기준이 아닌 꼭지점이 인덱스로 나와있어서 이 문제를 처음 접하시면 헷갈릴 수 있습니다. 그래서 저는 데이터를 넣을 때 

위 그림과 같이 생각을 한쪽 꼭지점과, 나머지 꼭짓점을 2중 for문을 돌려 범위 내에 있는 값들을 1로 넣어 모눈종이를 채웠습니다.

메인문에서 빈칸인 0을 발견하면 카운트를 후치 연산으로 하나 올려주고, bfs알고리즘을 돌려 빈칸 값을 반환받아 area배열에 넣어줬습니다.

만약 위 그림과 같이 빈 칸이 하나만 있는 경우, 빈칸을 찾아냈긴 했지만 제가 만든 bfs 로직으로는 0을 반환하기 때문에 빈칸 개수가 저장된 후 0이 반환되었으면 그 부분은 빈칸이 하나인 영역이므로 1로 바꿔줬습니다.

마무리 전에는 영역의 개수가 담긴 area배열을 오름차순으로 정렬해주고 출력해주었습니다.

x,y좌표를 헷갈리지 않도록 주의하면서 코드를 작성합시다.

 

코드

// 영역 구하기
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int paper[100][100];
int N,M,K;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
queue<pair<int,int>>q;
int bfs(){
    int cnt=0; //빈 칸이 하나밖에 없는 영역일 경우 그대로 빠져나와버림
    while(!q.empty()){
        int x=q.front().second;
        int y=q.front().first;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<0||ny<0||nx>=N||ny>=M)continue;
            if(!paper[ny][nx]){
                cnt++;
                paper[ny][nx]=1;
                q.push({ny,nx});
            }
        }  
    }
    return cnt;
}
int main(){
    int x1,x2,y1,y2,cnt=0,area[100];
    cin>>M>>N>>K;
    while(K--){
        cin>>x1>>y1>>x2>>y2;
        for(int i=y1;i<y2;i++)
            for(int j=x1;j<x2;j++)
                paper[i][j]=1;
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            if(!paper[i][j]){
                q.push({i,j});
                area[cnt++]=bfs();
                // 여기서 방금전에 area에 담긴 값이 0이면 1로 만들어 줌
                if(!area[cnt-1])area[cnt-1]=1;
            }
        }
    }
    sort(area,area+cnt);
    cout<<cnt<<"\n";
    for(int i=0;i<cnt;i++)cout<<area[i]<<" ";
}

2583번: 영역 구하기 (acmicpc.net)

2583번: 영역 구하기