[Baekjoon(백준)][2583번] 영역 구하기(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "영역 구하기" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 M×N 크기의 모눈종이에서 K개의 직사각형 영역이 주어졌을 때, 직사각형으로 덮이지 않은 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 각 영역의 넓이를 구하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

2583번: 영역 구하기

문제 개요

"영역 구하기" 문제는 M×N 크기의 모눈종이에서 K개의 직사각형 영역이 주어졌을 때, 직사각형으로 덮이지 않은 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 각 영역의 넓이를 구하는 문제입니다.

해결 방법

이 문제는 깊이 우선 탐색(DFS)을 사용하여 각 영역을 탐색하고, 탐색된 영역의 넓이를 계산합니다. 먼저 모눈종이 상에서 직사각형 영역을 표시하고, 이후 모눈종이의 각 점에서 DFS를 수행하여 분리된 영역을 찾습니다.

코드 구현

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

int m, n, k; // 모눈종이의 크기와 직사각형의 수
int table[105][105]; // 모눈종이의 각 점 상태
bool visited[105][105]; // 방문 여부

int dy[] = { 1,0,-1,0 }; // 상하좌우 이동
int dx[] = { 0,1,0,-1 };

// dfs 함수: 특정 영역 탐색
void dfs(int y, int x, int &count) {
    visited[y][x] = true;
    count++; // 영역의 크기 증가
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 0 && nx >= 0 && ny < m && nx < n && !visited[ny][nx] && table[ny][nx] == 0) {
            dfs(ny, nx, count); // 인접한 영역 탐색
        }
    }
}

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

    cin >> m >> n >> k;
    for (int i = 0; i < k; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        // 직사각형 영역 표시
        for (int x = a; x < c; x++) {
            for (int y = b; y < d; y++) {
                table[y][x] = 1;
            }
        }
    }

    vector<int> ret; // 각 영역의 넓이 저장
    for (int y = 0; y < m; y++) {
        for (int x = 0; x < n; x++) {
            if (!visited[y][x] && table[y][x] == 0) {
                int count = 0;
                dfs(y, x, count); // 영역 탐색
                ret.push_back(count); // 탐색된 영역의 크기 저장
            }
        }
    }

    sort(ret.begin(), ret.end()); // 영역의 크기 오름차순 정렬
    cout << ret.size() << "\n"; // 영역의 개수 출력
    for (auto it : ret) {
        cout << it << " "; // 각 영역의 크기 출력
    }
    cout << "\n";
}

코드 설명

이 코드는 주어진 직사각형들을 모눈종이에 표시한 뒤, 나머지 부분에 대해 DFS를 수행하여 분리된 영역을 찾습니다. 각 영역을 탐색할 때마다 해당 영역의 크기를 계산하고, 모든 영역을 찾은 후에는 영역의 크기를 오름차순으로 정렬하여 출력합니다.

결론

"영역 구하기" 문제는 DFS 알고리즘을 사용하여 2차원 평면 상의 분리된 영역을 찾고, 각 영역의 크기를 계산하는 문제입니다. DFS를 통해 효율적으로 각 영역을 탐색하고 계산하는 방법을 익히는 것이 중요합니다.