[DFS] 백준 2583번 - 영역 구하기 (정답률 56%)

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

2583번: 영역 구하기

백준 DFS 연습 문제다.

기존 2d 배열구조와 다른 좌표설정으로 문제에서 주어진 좌표들에 대해 변환작업을 고민해봐야한다.

이런것은 종이에 그림을 그리고 직접 해보며 규칙을 발견하면 된다.

 

아래는 dfs로 구현한 코드. (0ms)

 

#include<iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
vector<vector<bool> > map;
int M, N, K;
int small_ans;
vector<int> answer;
typedef struct dir{
    int dr, dc;
};
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void dfs(int r, int c){
    for (int i = 0; i < 4; i++){
        int nr = r + direction[i].dr;
        int nc = c + direction[i].dc;
        if (nr >= 0 && nr < M && nc >= 0 && nc < N){
            if (!map[nr][nc]){
                map[nr][nc] = true;
                small_ans++;
                dfs(nr, nc);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> M >> N >> K;
    map.assign(M, vector<bool>(N, false));
 
    for (int i = 0; i < K; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int r = M - y2; r < M - y1; r++){
            for (int c = x1; c < x2; c++){
                map[r][c] = true;
            }
        }
    }
    // 좌표 변환 및 true화 완료.
    for (int i = 0; i < M; i++){
        for (int j = 0; j < N; j++){
            if (!map[i][j]){
                small_ans = 0;
                map[i][j] = true;
                small_ans++;
                dfs(i, j);
                answer.push_back(small_ans);
            }
        }
    }
    sort(answer.begin(), answer.end());
    cout << answer.size() << '\n';
    for (int i = 0; i < answer.size(); i++){
        cout << answer[i] << " ";
    }
    return 0;
}