[BOJ 2583] 영역구하기

문제 출처

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

dfs로 풀이 했지만 bfs로 풀이하는게 더 좋을듯 하다. dfs는 모든 경우를 탐색할 수 있지만 계속적으로 탐색 하기 때문에 시간이 오래걸리는 단점이 존재한다. bfs풀이는 추가 업데이트를 하도록 하겠다. 

이 문제에서 가장 어려운건 맵을 그리는 거라 생각되는데 이해가 안된다면 종이에 그려보고 어떻게 for문을 돌려야 할지 생각해보면 금방 알 수 있다.

또한 눈금의 MAX값이 100이므로 결과를 나타낼 수 있는 배열은 100*100인 10000개를 선언해야 한다.

=> DFS 풀이

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 100
using namespace std;
int n,m,k,result;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
bool map[MAX][MAX];
void init() {
    scanf("%d %d %d", &n, &m, &k);
    int sx, sy, ex, ey;
    for (int i=0; i<k; i++) {
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        for (int y=sy; y<ey; y++) {
            for (int x=sx; x<ex; x++) {
                map[y][x]=1;
            }
        }
    }
}
bool isOutOfBoundMap(int y, int x) {
    if (x<0 || y<0 || x>=m || y>=n) return true;
    return false;
}
void dfs(int y, int x) {
    map[y][x]=1;
    result++;
    for (int i=0; i<4; i++) {
        int ny=y+dy[i];
        int nx=x+dx[i];
        if (isOutOfBoundMap(ny, nx) || map[ny][nx]) continue;
        dfs(ny, nx);
    }
}
void solve() {
    int areaCnt=0;
    vector<int> v;
    for (int y=0; y<n; y++) {
        for (int x=0; x<m; x++) {
            if (!map[y][x]) {
                ++areaCnt;
                dfs(y, x);
                v.push_back(result);
                result=0;
            }
        }
    }
    printf("%d\n", areaCnt);
    sort(v.begin(), v.end());
    for (int i=0; i<v.size(); i++) {
        printf("%d ", v[i]);
    }
}
int main() {
    init();
    solve();
    return 0;
}

=> BFS 풀이

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100
 
using namespace std;
int n,m,k;
int section=0;
bool map[MAX][MAX];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
queue<pair<int, int> > q;
vector<int> ret;
 
void init() {
    scanf("%d %d %d", &n, &m, &k);
    while(k--)
    {
        int x1,x2,y1,y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        for(int i=y2-1; i>=y1; i--)
            for(int j=x2-1; j>=x1; j--)
                map[i][j]=1;
    }
}
 
void bfs(int x, int y) {
    int cnt=1;
    map[x][y]=1;
    q.push(make_pair(x,y));
 
    while(!q.empty()) {
        x=q.front().first;
        y=q.front().second;
        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 && !map[nx][ny])
            {
                map[nx][ny]=1;
                q.push(make_pair(nx,ny));
                cnt++;
            }
        }
    }
    section++;
    ret.push_back(cnt);
}
 
int main(void) {
    init();
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(!map[i][j]) {
                bfs(i,j);
            }
        }
    }
 
    printf("%d\n", section);
    sort(ret.begin(), ret.end());
 
    for(int i=0; i<section; i++)
        print("%d ", ret[i]);
    return 0;
}