✅ BFS ✅ 연결요소

문제

링크

풀이

1. 문제 접근

1743 음식물 피하기 문제와 거의 유사한 문제로
연결요소의 수와 각 연결요소의 크기들을 구하는 문제이다.

2. 자료구조 or 알고리즘 선택과 그 이유

연결요소는 DFS, BFS 모두 풀이가 가능하지만 1743 음식물 피하기 에서 DFS로 풀어봤으니 이번 문제는 BFS로 풀어봤다.

3. 문제 해결 로직 (풀이법)

연결요소의 수와 각 연결요소의 크기들을 구하는 문제이므로 BFS를 한번 돌 때마다 집들의 수를 vector에 저장해놓고 마지막에 단지의 수(vector의 크기)와 총 집의 수(vector의 각 요소)를 출력하면 된다.

코드

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

using namespace std;

string map[26]; // 입력 문자 사이에 공백이 없으므로 문자열로 받아야 함
bool visited[26][26];
int N, cnt=0;        // 지도의 크기 N, 각 단지내 집의 수 cnt
vector<int> house; // 각 단지내 집의 수 저장
queue<pair<int,int>> que; // 좌표이므로 pair 사용

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

void BFS(int Y, int X){
    cnt = 1;
    visited[Y][X] = true;
    que.push({Y,X});

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

        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny < 0 || nx < 0 || ny > N || nx > N) continue;

            if(map[ny][nx] == '1' && visited[ny][nx] == false){
                visited[ny][nx] = true;
                que.push({ny, nx});
                cnt++;
            }
        }
    }

    house.push_back(cnt);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] == '1' && visited[i][j] == false){
                BFS(i,j);
            }
        }
    }

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

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

4. 시간 복잡도 분석

BFS는 완전탐색으로 인접 행렬을 통해 모든 좌표를 탐색했으므로
O(N^2)

5. 문제에서 중요한 부분

전형적인 연결요소 구하는 문제로 BFS를 떠올리는 것은 어렵지 않았다.
중요한 부분이라기 보다 편한 방법을 알게 되었는데
BFS를 돌 때마다 연결요소의 크기를 모두 vector에 저장하면
연결요소의 개수는 vector의 크기이므로 따로 카운트하지 않아도 된다는 것이다.