2583 : 영역 구하기 (C++)

2583번: 영역 구하기

---

알고리즘 문제 푸는데 있어서 2차원 배열과 수학에서 사용하는 그래프의 x축과 y축의 방향이 다르다 보니

헷갈렸었지만 이제는 거의 완벽하게 이해하고 문제를 풀 수 있는 것 같다.

먼저 크기 값과 직사각형의 갯수를 받고 좌표값들을 받은다음

직사각형 좌표들을 모두 방문처리 한다.

그다음 각각 DFS 또는 BFS를 실행하여 분리된 영역의 개수와 각 영역의 넓이를 vector에 입력받고

오름차순으로 정렬한 후 출력한다.

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

using namespace std;

#define MAX 100

int map[MAX][MAX];
bool visit[MAX][MAX];
vector<int> v;

int M, N, K;
int cnt = 0;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

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

    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
            if(visit[nx][ny] == false) {
                dfs(nx, ny);
            }
        }
    }
}

int main() {
    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++) {
                visit[x][y] = true;
            }
        }
    }

    for(int x = 0; x < N; x++) {
        for(int y = 0; y < M; y++) {
            if(visit[x][y] == false) {
                cnt = 0;
                dfs(x, y);
                v.push_back(cnt);
            }
        }
    }

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

    cout << v.size() << endl;

    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ' ';
    }

    return 0;
}

 

밑에 방식은 BFS함수 코드

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visit[x][y] = true;

    cnt = 1;

    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if(visit[nx][ny] == false) {
                    q.push({nx, ny});
                    visit[nx][ny] = true;
                    cnt++;
                }
            }
        }
    }
}