백준 2667번: 단지번호붙이기 C++ 코드(BFS)

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>


using namespace std;

int graph[26][26];
int tt[300];
int n;
int count1;
int x[4] = {0,0,-1,1};
int y[4] = {-1,1,0,0};

int bfs(int xx, int yy){
    queue<pair <int, int> > q;
    pair<int, int> now = make_pair(xx,yy);
    q.push(now);
    int ccoouunntt = 0;
    int state = 0;
    while(!q.empty()){
        ccoouunntt += 1;
        now = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int xxx = now.first + x[i];
            int yyy = now.second + y[i];
            if(0 <= xxx & xxx < n & 0 <= yyy & yyy < n & graph[xxx][yyy] == 1){
                q.push(make_pair(xxx,yyy));
                graph[xxx][yyy] = 0;
                state = 1;
            }
        }
    }
    if(state == 1){
        return ccoouunntt - 1;
    }else{
        return ccoouunntt;
    }
}

int main(){
    count1 = 0;

    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        for(int j = 0; j< n; j++){
            scanf("%1d", &graph[i][j]);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(graph[i][j] == 1){
                tt[count1] = bfs(i,j);
                count1 += 1;
            }
        }
    }
    printf("%d\n",count1);
    sort(tt,tt+count1);
    
    for(int i = 0; i< count1; i++){
        printf("%d\n", tt[i]);
    }
}

설명

평소에 파이썬으로만 풀이하다가 오랜만에 c++ 문법도 되살릴겸 c++로 풀어봤다.(물론 c++ 를 c처럼 사용하긴 하지만...)

평범한 bfs문제로 그래프를 [0][0] 인덱스부터 검사하여, 1이 나오면 bfs함수로 넘겨줘서 같이 붙어있는 칸이 몇칸인지 세어서 리턴해주면 된다.

 

문제점

bfs함수를 만들때, 한칸있을때 카운트하는 것에 문제가 생겨서 시간이 조금 걸렸다.