백준 | 2583. 영역구하기

 

 

1. idea

• 세로, 가로, 직사각형 개수를 입력받고, 개수 만큼 직사각형의 각 꼭짓점을 입력받는다
• vector를 전부 0으로 채운 다음 이중 for문으로 (꼭지점 시작 x ~ 끝 x), (꼭지점 시작 y ~ 끝 y) 돌면서 1로 변경
• 그다음 map 돌면서 0 만나면 dfs 시작, dfs 내에서 방문은 1로 변경 처리 + 넒이 count, ans vector에 dfs 끝나고 나온 size 값 push_back()
• ans sort(오름차순) 하고 ans size랑 ans 내부 요소들 cout

 

2 DFS 함수 만들기

int dfs(vector<vector<int>>&map, int x, int y, int ex, int ey){
    int dx[] = {0, 0, -1, 1};
    int dy[] = {1, -1, 0, 0};

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

        if(nx >= 0 && nx < ex && ny >= 0 && ny < ey){
            if(!map[ny][nx]) cnt += dfs(map, nx, ny, ex, ey);
        }
    }
    return cnt;
}

 

 

 

3. 전체 지도 순회

    vector<int>ans;

    for(int i = 0; i < R; ++i){
        for(int j = 0; j < C; ++j){
            if(!map[i][j]){
                int size = dfs(map, j, i, C, R);
                ans.push_back(size);
            }
        }
    }​

 

 

4. 코드 전문

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dfs(vector<vector<int>>&map, int x, int y, int ex, int ey){
    int dx[] = {0, 0, -1, 1};
    int dy[] = {1, -1, 0, 0};

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

        if(nx >= 0 && nx < ex && ny >= 0 && ny < ey){
            if(!map[ny][nx]) cnt += dfs(map, nx, ny, ex, ey);
        }
    }
    return cnt;
}

int main(){
    int C, R, X;

    cin >> R >> C >> X;
    vector<vector<int>>map(R, vector<int>(C,0));
    int sx, sy, ex, ey;
    while(X--){
        cin >> sx >> sy >> ex >> ey;
        for(int i = sy; i < ey; ++i){
            for(int j = sx; j < ex; ++j){
                map[i][j] = 1;
            }
        }
    }

    /*for(int i = 0; i < R; ++i){
        for(int j = 0; j < C; ++j)cout << map[i][j] << " ";
        cout << endl;
    }*/ // vector 입력 확인

    vector<int>ans;

    for(int i = 0; i < R; ++i){
        for(int j = 0; j < C; ++j){
            if(!map[i][j]){
                int size = dfs(map, j, i, C, R);
                ans.push_back(size);
            }
        }
    }

    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for(auto x : ans) cout << x << " ";
    
    return 0;
}