[BOJ/C++] 영역 구하기(2583번)

1. 개요

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

2583번: 영역 구하기

1-1. 설명

눈금 간격이 1인 MxN 크기 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇개의 분리된 영역으로 나누어진다. 

나누어진 영역

위의 <그림 2>처럼 영역의 넓이가 3개로 나눠지는 것을 확인할 수 있다. M,N과 K 그리고 K개의 직사각형 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지 구해 이를 출력하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 M과 N, K가 빈칸을 두고 차례로 주어지며, 모두 100 이하의 자연수

 - 둘째 줄부터 K개 줄에는 한줄에 하나씩 직사각형 왼쪽 아래 꼭짓점의 x,y 좌표값과 오른쪽 위 꼭짓점의 x,y 좌표값이 빈칸을 사이에 두고 차례로 주어짐

---

2. 구현

2-1. 풀이

좌표를 잘 저장해 DFS로 풀면 된다. DFS는 어렵지 않으나, 좌표를 저장하는 과정에서 어떤식으로 저장해야할지 잘 생각해야 했었다. 좌표만 잘 저장하면 그리 어려운 문제는 아니었다. 

2-2. 코드

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    int x, y;
};

int dirX[4] = {0, 0, 1, -1};
int dirY[4] = {1, -1, 0, 0};
int maps[101][101];
bool visited[101][101];
vector<int> results;
int cnt = 0, M, N;
stack<Node> st;

void DFS(int x, int y);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int K, startX, startY, endX, endY;
    cin >> M >> N >> K;

    for (int i = 0; i < K; i++) {
        cin >> startX >> startY >> endX >> endY;
        for (int x = startY; x < endY; x++) {
            for (int y = startX; y < endX; y++) maps[x][y] = 1;
        }
    }

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j] && maps[i][j] == 0) {
                cnt = 0;
                DFS(i, j);
                results.push_back(cnt);
            }
        }
    }
    cout << results.size() << "\n";
    sort(results.begin(), results.end());
    for (int res : results) {
        cout << res << ' ';
   }
    return 0;
}

void DFS(int x, int y) {
    st.push({ x,y });
    while (!st.empty()) {
        Node cur = st.top();
        st.pop();
        if (visited[cur.x][cur.y]) continue;
        cnt += 1;
        visited[cur.x][cur.y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = cur.x + dirX[i];
            int nextY = cur.y + dirY[i];
            if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N || maps[nextX][nextY] == 1)  continue;
            st.push({ nextX, nextY });
        }
    }
}