[백준 2583] 영역 구하기 - C++ / 알고리즘 DFS

문제

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

2583번: 영역 구하기

나의 코드

bfs 코드를 많이 풀었지 dfs는 푼 경험이 없는 것 같아서 dfs로 풀어보았다.

앞으로 배울 백트래킹 알고리즘에 도움이 되기 위해!

dfs에서 주의할 점은 일단 인접한 노드는 방문표시를 하고 스택에 집어넣는다.

그래야지 방문한 인접 노드를 또 방문하는 패해를 없앤다.

물론 스택에서 나온 현재 보는 노드가 이미 방문 표시가 되었음을 인지하자.

그러나 dfs는 "재귀함수"로도 풀이될 수 있음을 알자.(오히려 재귀함수가 더 깔끔하다. 근데 내가 재귀함수를 싫어해서;;;)

재귀함수 풀이 참고 : https://rile1036.tistory.com/48

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int m, n, k;
stack <pair<int, int> > stk;  //x, y
int domain[100][100] = { 0 }; // 0:색칠x, 1: 색칠o
int visited[100][100] = { 0 }; //0:방문x, 1: 방문o
vector<int> area_array;  //넓이 저장
int direct[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
 
void dfs() {
    for(int y = 0;y< m;y++){
        for (int x = 0; x < n; x++) {
            if (domain[y][x] == 0 && visited[y][x] == 0) {
                int domain_area = 0;  //영역 넓이
 
                stk.push(make_pair(x, y));
                visited[y][x] = 1;
 
                //dfs
                while (!stk.empty()) {
                    pair<int, int> now = stk.top();
                    stk.pop();
                    domain_area++;
 
                    for (int i = 0; i < 4; i++) {
                        pair<int, int> next = make_pair(now.first + direct[i][0], now.second + direct[i][1]);
                        if (next.first >= 0 && next.first <= n - 1 && next.second >= 0 && next.second <= m - 1 && domain[next.second][next.first] == 0 && visited[next.second][next.first] == 0) {
                            stk.push(next);
                            visited[next.second][next.first] = 1;
                        }
                    }
                }
                area_array.push_back(domain_area);
            }
        }
    }
}
 
int main(void) {
    cin >> m >> n >> k;
    
    for (int i = 0; i < k; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
 
        x2--;
        y2--;
 
        for (int i = y1; i <= y2; i++) {
            for (int j = x1; j <= x2; j++) {
                domain[i][j] = 1;
            }
        }
    }
 
    dfs();
    cout << area_array.size() << '\n';
    sort(area_array.begin(), area_array.end());
    for (int i = 0; i < area_array.size(); i++)
        cout << area_array[i] << ' ';
}

 

dfs 공부 출처 : https://blog.encrypted.gg/729?category=773649