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

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

 

 

이 문제는 1로 이어진 아파트 단지 수와 각 단지내 집의 수를 오름차순으로 출력하는 문제이다.

 

 

풀이

n의 갯수 만큼 이중 for문을 돌려 아직 방문하지 않은 1을 찾고, 해당 위치에서 bfs를 이용해 이어져있는 1을 탐색한다.

 

탐색이 완료되면 1의 갯수를 answer 벡터에 Push 한 뒤, 모든 탐색이 완료되면 answer 벡터를 오름차순으로 정렬하고 벡터의 size와 0부터 순서대로 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
// https://www.acmicpc.net/problem/2667
using namespace std;

int n;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void BFS(vector<string> map, vector<vector<bool>> visited)
{
    vector<int> answer;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j] && map[i][j] == '1') { 
                int count = 1;
                queue<pair<int,int>> q;
                q.push({ i,j });
                visited[i][j] = true;

                while (!q.empty()) {  // bfs
                    pair<int,int> p = q.front();
                    q.pop();

                    for (int k = 0; k < 4; k++) {
                        int x_Pos = p.first + dx[k];
                        int y_Pos = p.second + dy[k];

                        if (x_Pos >= 0 && x_Pos <= n -1 && y_Pos >= 0 && y_Pos <= n - 1 
                            && map[x_Pos][y_Pos] == '1' && !visited[x_Pos][y_Pos]) {
                            visited[x_Pos][y_Pos] = true;
                            q.push({ x_Pos, y_Pos });
                            count++;
                        }
                    }
                }
                answer.push_back(count);
            }
        }
    }

    // 결과 출력
    cout << answer.size() << endl;
    sort(answer.begin(), answer.end());
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << endl;
    }
}
int main() {
    int x;

    cin >> n;

    // n 만큼 벡터 크기 정의
    vector<string> map(n);
    vector<vector<bool>> visited(n , vector<bool>(n,false));

    string str;
    for (int i = 0; i < n; i++) {
        cin >> str;
        map[i] = str;
    }

    BFS(map, visited);

    return 0;
}