공부흔적

문제 링크

풀이 )

  처음 모눈종이의 모든 칸이 false이므로 , 주어지는 직사각형이 덮는 영역을 true로 고쳐준 후

(0, 0)을 시작으로 덮지 않은, 즉 칸이 false이고, 방문여부 또한 false인 칸을 찾아

DFS를 사용하여 영역의 넓이를 구해 vector에 넣어준다.

  마지막 칸까지 확인한 후 vector에 들어가있는 영역의 넓이를 정렬해준 뒤 출력한다.

* 문제에서는 좌하단을 (0, 0)으로 잡았기 때문에 내가 생각한 그림과 상하반전이 되어있지만, 결괏값에 영향을 주지 않는다.

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

using namespace std;

int n, m, k, area;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool arr[100][100];
bool visited[100][100];
vector<int> vc;

void dfs(int x, int y){
    visited[x][y] = true;
    area++;
    for(int dir = 0; dir < 4; ++dir){
        int xx = x+dx[dir];
        int yy = y+dy[dir];
        if(xx < 0 || xx >= n || yy < 0 || yy >= m)
            continue;
        if(arr[xx][yy] || visited[xx][yy])
            continue;
        dfs(xx, yy);
    }
    return;
}

int main(void){
    cin >> n >> m >> k;
    int cnt = 0;
    while(k--){
        int lx, ly, rx, ry;
        cin >> ly >> lx >> ry >> rx;
        for(int x = lx; x < rx; ++x){
            for(int y = ly; y < ry; ++y){
                arr[x][y] = true;
            }
        }
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(!arr[i][j] && !visited[i][j]){
                cnt++;
                area = 0;
                dfs(i, j);
                vc.push_back(area);
            }
        }
    }

    sort(vc.begin(), vc.end());
    cout << cnt << endl << vc.front();
    for(vector<int>::iterator it = vc.begin()+1; it != vc.end(); ++it)
        cout << ' ' << *it;
    cout << endl;
}

주의 )

- 문제에서 주어지는 입력순서 m, n, k는 세로, 가로 이지만 이후 k줄에 대해서는 x, y 순서로 주어진다.