[BOJ / C++] #2267 단지번호붙이기

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

😇 BFS로 풀었는데 왜.. 왜 대체 안돌아가나 애먹었는데 큐에서 pop을 빼먹었다 컄캬컄ㅋ캐컄

문제 풀이

간단한 BFS/DFS 문제다.
입력을 char형으로 받고 , visited 배열을 사용해주었다.

BFS

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

using namespace std;
#define MAX 25
char map[MAX+1][MAX+1];
bool visited[MAX+1][MAX+1];
int N;
vector<int> res;

int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};

void bfs(int r,int c){
    int cnt=0;

    queue<pair<int,int>> q;
    visited[r][c]=true;
    q.push(make_pair(r,c));
    cnt++;

    while(!q.empty()){
        int cr=q.front().first;
        int cc=q.front().second;
        
        // 빼먹지 말기 🦧
        q.pop();

        for(int d=0;d<4;d++){
            int nr=cr+dr[d];
            int nc=cc+dc[d];

            if(nr<0||nr>N-1||nc<0||nc>N-1||map[nr][nc]!='1'||visited[nr][nc]) continue;

            visited[nr][nc]=true;
            q.push(make_pair(nr,nc));
            cnt++;
        }
    }
    res.push_back(cnt);
}


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(map[i][j]=='1'&&!visited[i][j]){
                bfs(i,j);
            }
        }
    }

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

    cout<<res.size()<<"\n";
    for(int i:res){
        cout<<i<<"\n";
    }
}

DFS

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 25
char map[MAX+1][MAX+1];
bool visited[MAX+1][MAX+1];
int N;
vector<int> res;
int cnt;

int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};

void print(int i, int j){
    cout<<"ii\n";
}

void dfs(int r, int c){
    visited[r][c]=true;
    cnt++;

    for(int d=0;d<4;d++){
        int nr=r+dr[d];
        int nc=c+dc[d];

        if(nr<0||nr>N-1||nc<0||nc>N<-1||map[nr][nc]!='1'||visited[nr][nc]) continue;
        dfs(nr,nc);
    }
}


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(map[i][j]=='1'&&!visited[i][j]){
                cnt=0;
                dfs(i,j);
                res.push_back(cnt);
            }
        }
    }

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

    cout<<res.size()<<"\n";
    for(int i:res){
        cout<<i<<"\n";
    }
}

이런 문제 보면 무조건 BFS로 시도하는데, DFS로도 많이 푸는 거 같다.. 코드 수도 적고