[백트래킹]2583번 영역 구하기

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

백트래킹 문제 어떻게 풀지?

1. 먼저 Map에 직사각형의 부분을 채운다.  => 코드의 making 부분

2. dfs를 사용하여 영역의 크기를 구한다.

※필요 역량 정리하기!!!※

1. dfs + 백트래킹

2. #include<vector> 정리

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int m, n,k;
int map[101][101];
int visit[101][101] = { 0 };
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };
 
void making(int x1, int y1, int x_len, int y_len) {
    for (int y = y1; y < y1 + y_len; y++) {
        for (int x = x1; x < x1 + x_len; x++) {
            map[x][y] = 1;
        }
    }
}
 
 
int dfs(int x, int y) {
    
    int cnt = 1;
 
    map[x][y] = 1;
    visit[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (map[nx][ny] != 1 &&visit[nx][ny] != 1 && nx >= 0 && nx < n && ny >= 0 && ny < m) {
            cnt += dfs(nx, ny);
        }
    }
    return cnt;
}
int main() {
    int cnt=0;
    cin >> m >> n>>k;
    for (int i = 0; i < k; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        making(x1, y1, x2 - x1, y2 - y1);
    }
 
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visit[i][j] && map[i][j] == 0) {
                ans.push_back(dfs(i, j));
            }
        }
    }
 
 
    cout << ans.size() << endl;
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    return 0;
}