백준 2583 - 영역구하기

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

2583번: 영역 구하기

문제 

---

백준의 단지 수 문제와 같은 유형처럼 행렬에 나뉘어진 땅덩어리를 구하기 각 땅덩어리가 차지하는 면적을 구하는 문제이다

 

문제 풀이

---

위의 문제는 DFS 또는 BFS 두 방법 모두로 풀수 있다. 하지만 필자는 상하좌우로 푸는 것을 선호하여 BFS로 문제 풀이를 진행했습니다.

 

코드 

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int dx[4] = {-1, 0, 1, 0};	//각각의 상하좌우를 보기 위한 장치
int dy[4] = {0, -1, 0, 1};
int cnt=0,area=0;

int mat[100][100]={0,};
int isvisit[100][100]={0,};
int M,N,K;
queue<pair<int,int> >q;	//BFS로 풀기위한 queue 장치
vector<int>v;	//BFS를 실행할때마다 나오게 되는 면적을 저장하는 vector

bool chk(int x,int y){	//상하좌우를 비교할때 존재하는 좌표임을 check하는 함수
    if ((x >= 0 && x < M) && (y >= 0 && y < N)) return true;
    return false;
}

void bfs(int x,int y){	//BFS 함수
    q.push(make_pair(x,y));
    isvisit[x][y]=1;
    while(!q.empty()){
        int curx=q.front().first;
        int cury=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=curx+dx[i];
            int ny=cury+dy[i];
            if (chk(nx,ny)==true){
                if (mat[nx][ny]==0 && isvisit[nx][ny]==0){
                    area+=1;
                    isvisit[nx][ny]=1;
                    q.push(make_pair(nx,ny));
                }
            }
        }
    }
    v.push_back(area);	//영역의 널비 저장
}
// void print(int a[][100]){	//프린트로 결과를 확인해보기 위한 프린트 함수
//     for (int i = 0; i < M; i++)
//     {
//         for (int j = 0;j < N; j++)
//         {
//             printf("%d",a[i][j]);
//         }
//         printf("\n");
//     }
// }

int main(){
    scanf("%d %d %d",&M,&N,&K);
    int x,y,xx,yy;
    for(int i=0;i<K;i++){
        scanf("%d %d %d %d \n",&y,&x,&yy,&xx);
        for(int i=y;i<yy;i++){
            for(int j=M-xx;j<M-x;j++){
                mat[j][i]=1;
            }
        }
        
    }
    memset(isvisit,0,sizeof(isvisit));	//memset을 이용한 isvisit 초기화
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            area=1;
            if(isvisit[i][j]==0&& mat[i][j]==0){
                cnt+=1;area=1;
                bfs(i,j);
            }
        }
    }
    printf("%d\n",cnt);
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++) printf("%d ",v[i]);
}

Funny algorithms :)