[백준 2667][C++] 단지번호붙이기 (Silver 1)

[문제보기]

 2667. 단지번호붙이기

2667번: 단지번호붙이기

 

[풀이과정]

BFS 알고리즘을 이용하여 문제를 풀었다. BFS 알고리즘으로 인해 인접하고 있는 단지가 몇 개인지 세 본후,

vector v에 저장한다. 이 연산을 이중 포문을 통해 모든 map에 대해 검사를 하는데 이 때, check[][] 배열을 통해

이미 검사를 했던 곳은 건너 뛰고, map[i][j] == 0인 경우에도 건너 뛴다.

 

vector v에 저장을 다 하고 난 뒤 오름차순으로 출력을 해야되므로 sort()함수를 사용하여 vector v를 정렬한 뒤

출력한다.

[소스코드]

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int map[25][25] = {0};
bool check[25][25] = {0};
pair<int, int> movdir[4] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
vector<int> v;

void bfs(int sy, int sx){
    queue<pair<int, int>> q;
    q.push({sy, sx});
    check[sy][sx] = false;
    int cnt = 1;

    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nexty = y + movdir[i].first;
            int nextx = x + movdir[i].second;
            
            if(nexty < 0 || n <= nexty || nextx < 0 || n <= nextx) continue;
            if(map[nexty][nextx] == 0) continue;

            if(check[nexty][nextx] == true){
                check[nexty][nextx] = false;
                q.push({nexty, nextx});
                cnt++;
            }
        }
    }

    v.push_back(cnt);
}

int main(){
    memset(check, true, sizeof(check));
    cin >> n;

    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        for(int j=0; j<n; j++){
            map[i][j] = s[j] - '0';
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(map[i][j] == 0) continue;
            if(check[i][j] == false) continue;

            bfs(i, j);
        }
    }

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

    cout << v.size() << "\n";
    for(int i=0; i<v.size(); i++){
        cout << v[i] << "\n";
    }
}

 

[해결 과정 중 실수한 부분]