[BOJ알고리즘, C++]#2583_영역 구하기, DFS, 미로 찾기

#1. 문제

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

 

---

 

#2. 풀이

 

1. DFS

[자료구조]#6_그래프

DFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 현재 경로에서 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색하는 방법입니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 통해 구현 가능합니다.

 

2. 직사각형 영역은 방문 여부를 미리 체크해 놓고, 그 외 영역을 탐색하자!

1. 먼저, 2차원 벡터 컨테이너를 활용하여 그래프를 구성합니다.
2. 그리고, 2차원 벡터 컨테이너를 황룡하여 방문여부를 준비합니다.
3. 그리고, 직사각형 영역들을 순회하며 방문여부를 참으로 변경해 줍니다.
4. 마지막으로, 방문 여부가 거짓인 영역들을 시작으로 DFS를 수행하며 각 칸의 개수를 구하여 합해줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/2583
*   @문제: MxN 크기의 모눈종이에 K개의 직사각형을 그릴 때, 직사각형 외부의 영역들의 갯수 출력, 그리고 각 넓이를 오름차순으로 출력
*   @설명
        1. 직사각형 영역을 방문 여부로 체크
        2. DFS 수행하면서 방문여부 체크와 동시에 넓이 계산
        3. DFS 수행 횟수, 그리고 각 DFS의 결과 값을 저장
*/


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

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

    return 0;
}

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

int M, N, K;
vector<vector<bool>> visited;
vector<int> areas;
int dy[] = {1,-1,0,0};
int dx[] = {0,0,1,-1};

void dfs(int y, int x, int& cnt)
{
    cnt++;
    visited[y][x] = true;

    for(int i=0; i<4; ++i)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny < 0 || ny >= M || nx < 0 || nx >= N || visited[ny][nx]) continue;

        dfs(ny, nx, cnt);
    }
}

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

    cin >> M >> N >> K;
    visited.resize(M, vector<bool>(N, false));

    while(K--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for(int y = y1; y < y2; ++y)
        {
            for(int x = x1; x < x2; ++x)
            {
                visited[y][x] = true;
            }
        }
    }

    for(int i=0; i<M; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            if(!visited[i][j])
            {
                int cnt = 0;
                dfs(i, j, cnt);
                areas.push_back(cnt);
            }
        }
    }

    sort(areas.begin(), areas.end());

    cout << areas.size() << '\n';
    for(int area : areas)
        cout << area << ' ';

    return 0;
}

 

---