백준 2583 영역 구하기(dfs)

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

2583번: 영역 구하기

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

using namespace std;
const int MAX = 100;
int M, N, K;
bool visited[MAX][MAX];
int cnt;
typedef struct
{
    int x, y;
} Dir;
Dir Dirmove[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int domain;
vector<int> answer;

void dfs(int x, int y)
{
    domain++;
    visited[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
        int nextX = x + Dirmove[i].x;
        int nextY = y + Dirmove[i].y;
        if (0 <= nextX && nextX < M && 0 <= nextY && nextY < N && !visited[nextX][nextY])
            dfs(nextX, nextY);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> M >> N >> K;
    for (int i = 0; i < K; i++)
    {
        int x1, y1, x2, y2;
        cin >> y1 >> x1 >> y2 >> x2; //도형을 위아래로 뒤집는다 생각.
        for (int i = x1; i < x2; i++)
            for (int j = y1; j < y2; j++)
                visited[i][j] = true;
    }
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (!visited[i][j])
            {
                cnt++;
                dfs(i, j);
                answer.push_back(domain);
            }
            domain = 0;
        }
    }
    cout << cnt << "\n";
    sort(answer.begin(), answer.end());
    for (int i = 0; i < answer.size(); i++)
        cout << answer[i] << " ";
}

이것 또한 전형적인 dfs 모양으로 풀 수 있었던 문제. 크게 어려운 부분은 없었지만 그래프의 좌표가 일반적인 경우와는 조금 다르다는게 포인트였다. 어떻게 푸는게 좋을까 생각하다가 그냥 그래프를 위 아래로 뒤집으면 쉽게 볼 수 있다는 것을 알게 되었다.