[bfs, dfs] 백준 2667 단지번호붙이기

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

저에게 익숙한 bfs로 짠 코드 입니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int main(){
    char map[25][25];
    int ret[625] = {0};
    int n, idx= -1;
    queue<pair<int,int> > q;
    bool visited[25][25] = {0};
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
 
    cin >> n;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) cin >> map[i][j];
    }
 
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(visited[i][j] || map[i][j] == '0') continue;
            
            idx+=1;
            q.push({i,j});
            visited[i][j] = 1;
            ret[idx] =0;
            
            while(!q.empty()){
                int x = q.front().second, y = q.front().first;
                q.pop();
                ret[idx] += 1;
                
                for(int k = 0; k < 4; k++){
                    int xx = x + dx[k], yy = y + dy[k];
                    
                    if(xx >= n || xx < 0 || yy >=n || yy < 0) continue;
                    if(visited[yy][xx] || map[yy][xx] == '0') continue;
                    
                    
                    q.push({yy,xx});
                    visited[yy][xx] = 1;
                }
            }
        }
    }
    
    sort(ret, ret+idx+1);
    
    cout << idx+1 << '\n';
    for(int i = 0; i <= idx; i++)
        cout << ret[i] << '\n';
}

이번에 소학회에서 배운 dfs로 구현해봤습니다. 연습하면 dfs로 구현하는 것이 더 쉬울 것 같네요.

#include <iostream>
#include <algorithm>
using namespace std;
 
int ret[625] = {0}, n, idx=-1;
bool visited[25][25] = {0};
char map[25][25];
 
void dfs(int y, int x){
    if(y >= n || y < 0 || x >= n || x < 0 || map[y][x] =='0' || visited[y][x]) return;
    ret[idx]++;
    visited[y][x] = 1;
    dfs(y-1,x), dfs(y+1,x) , dfs(y,x-1), dfs(y,x+1);
}
 
int main(){
    cin >> n;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            cin >> map[i][j];
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(visited[i][j] || map[i][j] == '0') continue;
            idx++;
            dfs(i,j);
        }
    }
    sort(ret, ret+idx+1);
    
    cout << idx+1 << '\n';
    for(int i = 0; i <= idx; i++)
        cout << ret[i] << '\n';
}