[DFS] 백준 2667번 - 단지번호붙이기 (정답률 38%)

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

2667번: 단지번호붙이기

백준 DFS 연습 문제다.

바로 전에 풀었던 1012번(유기농 배추, https://cpp-dev.tistory.com/22)과 유사한 문제다.

전체 map을 돌면서 방문하지 않았고, 아파트가 있는 곳이면 dfs 탐색으로 해당 아파트의 단지를 모두 방문한뒤, 동일한 과정을 이어나가며 총 단지의 개수 및 그 단지마다 있는 아파트의 개수를 구하면 된다.

 

벡터에 정답들을 담아넣고 <algorithm>의 sort 함수로 출력해도 되었으나 그냥 priority_queue를 연습할 겸 써봤다.

 

#include <iostream>
#include <queue>
#include <string>
#include <functional>
#define maxlen 25
 
using namespace std;
int map[maxlen][maxlen];
bool check[maxlen][maxlen];
int N;
int cur_ans = 0;
priority_queue<int, vector<int>, greater<int> > pq_answer;
 
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void reset(){
    for (int i = 0; i < maxlen; i++){
        for (int j = 0; j < maxlen; j++){
            map[i][j] = 0;
            check[i][j] = false;
        }
    }
}
 
void dfs(int r, int c){
    check[r][c] = true;
    cur_ans++;
    for (int i = 0; i < 4; i++){
        int n_r = r + direction[i].dr;
        int n_c = c + direction[i].dc;
        if (n_r >= 0 && n_r < N && n_c >= 0 && n_c < N){
            if (!check[n_r][n_c] && map[n_r][n_c]){
                dfs(n_r, n_c);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string str;
    reset();
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> str;
        for (int j = 0; j < str.length(); j++){
            if (str[j] == '0')
                map[i][j] = 0;
            else
                map[i][j] = 1;
        }
    }
    for (int r = 0; r < N; r++){
        for (int c = 0; c < N; c++){
            if (!check[r][c] && map[r][c]){
                dfs(r, c);
                pq_answer.push(cur_ans);
                cur_ans = 0;
            }
        }
    }
    int loop_cnt = pq_answer.size();
    cout << loop_cnt << '\n';
    for (int i = 0; i < loop_cnt; i++)
    {
        cout << pq_answer.top() << '\n';
        pq_answer.pop();
    }
    return 0;
}