[백준] 2583 영역 구하기 c++

 

문제 링크 https://www.acmicpc.net/problem/2583

KEY

• 입력형식을 적절하게 바꾸어서 색칠된 부분을 표현하는 것이 중요했다.
• 나같은 경우는 좌표형식을 배열인덱스로 갖고 오고자 x좌표와 y좌표를 뒤집었다.(모양은 뒤집어지지만 넓이는 같다)
• ex) 테스트케이스에서 예시를 들어보면, 좌표값 (4,0), (6 2)를 뒤집어 (0,4),(2,6)를 만들고, 이는 배열 arr[0][4]에서 arr[1][5]까지 색칠되었다고 표현할 수 있다. 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 101;
int m, n, k;
int arr[MAX][MAX];
bool visited[MAX][MAX];
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
vector<int> answer;
int dist;
 
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (visited[nx][ny])
            continue;
        if (nx < 0 || nx >= m || ny < 0 || ny >= n)
            continue;
        if (arr[nx][ny] == 1)
            continue;
        visited[nx][ny] = true;
        dist = dist + 1;
        dfs(nx,ny);
    }
}
int main()
{
    cin >> m >> n >> k;
    for (int i = 0; i < k; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int j = y1; j < y2; j++) {
            for (int k = x1; k < x2; k++) {
                arr[j][k] = 1;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 0 && visited[i][j] == 0) {
                dist = 1;
                visited[i][j] = true;
                dfs(i, j);
                answer.push_back(dist);
            }
        }
    }
 
    sort(answer.begin(), answer.end());
    cout << answer.size() << endl;
    for (int i : answer)
        cout << i << " ";
 
}