백준 2583번 영역 구하기 - C++ 풀이

---

 

1. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 잇는다.
2. 완성된 그래프에서 각 연결 요소의 크기와 연결 요소의 개수를 센다.

 

1. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 잇는다.

 유의미한 칸은 직사각형이 없는 칸이다. 직사각형이 없는 칸을 그래프의 노드로 생각하고, 인접한 모든 노드를 간선으로 이어 그래프로 만들어준다.

 

2. 완성된 그래프에서 각 연결 요소의 크기와 연결 요소의 개수를 센다.

 이제 각 영역은 연결 요소와 같다. DFS/BFS로 연결 요소의 개수를 세는 동시에 각 연결 요소의 크기도 구해준다. 연결 요소의 개수는 총 DFS/BFS의 호출 횟수이고, 각 연결 요소의 크기는 한 DFS/BFS에서 방문한 노드의 개수와 같다.

 

반응형

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int M, N, K;
bool board[100][100];
bool visit[100][100];

int DFS(int r, int c) {
    if (visit[r][c]) return 0;
    visit[r][c] = true;
    
    int ret = 1;
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    for (int i=0; i<4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
        if (visit[nr][nc] || board[nr][nc]) continue;
        ret += DFS(nr, nc);
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> M >> N >> K;
    for (int i=0; i<K; i++) {
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        for (int r=sy; r<ey; r++) {
            for (int c=sx; c<ex; c++) {
                board[r][c] = true;
            }
        }
    }
    
    vector<int> ans;
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
            if (board[i][j] || visit[i][j]) continue;
            ans.push_back(DFS(i, j));
        }
    }
    sort(ans.begin(), ans.end());
    
    cout << ans.size() << "\n";
    for (auto sz: ans) cout << sz << " ";

    return 0;
}