백준 2667 단지번호붙이기 - C++

접근

그래프 문제라고 생각하면 문제에 쉽게 접근할 수 있다.

핵심 개념은 연결 요소가 무엇인지 DFS 또는 BFS가 무엇인지 알고 있으면 좋다.

각 단지는 서로 연결되어 있지 않기 때문에 각각을 연결 요소라고 생각해도 좋다.

각 집은 어떠한 집 기준으로 상하좌우 중 한 곳에 위치해 있으면 연결되어 있다고 본다.

행렬에서 어떠한 집(A[i][j])에서 상하좌우는 (i,j-1),(i,j+1), (i-1, j), (i+1,j)의 값과 동일하다.

 

DFS

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
int A[26][26]; 
bool check[26][26];
vector<int> vectorCnt;
int cnt = 0;
void dfs(int i, int j){
    check[i][j] = true;
    cnt++;
    // 현재 i행 j열 기준 상하좌우 (i,j-1),(i,j+1), (i-1, j), (i+1,j)를 비교
    if(A[i][j-1] == 1 && check[i][j-1] != true) dfs(i, j-1);
    if(A[i][j+1] == 1 && check[i][j+1] != true) dfs(i, j+1);
    if(A[i-1][j] == 1 && check[i-1][j] != true) dfs(i-1, j);
    if(A[i+1][j] == 1 && check[i+1][j] != true) dfs(i+1, j);
}

int main()
{
    int N;
    scanf("%d", &N);
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            scanf("%1d", &A[i][j]);
        }
    }
    int elCnt = 0;
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(check[i][j] != true && A[i][j] == 1) {
                dfs(i,j);
                vectorCnt.push_back(cnt);
                cnt = 0;
                elCnt++;
            }
        }
        
    }
    sort(vectorCnt.begin(), vectorCnt.end());
    cout << elCnt << '\n';
    for(int i=0; i<vectorCnt.size(); i++){
        cout << vectorCnt[i] << '\n';
    }
    return 0;
}

 

BFS

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int A[26][26]; 
bool check[26][26];
vector<int> vectorCnt;
int low[] = {-1,+1,0,0};
int col[] = {0,0,-1,+1};
int bfs(int i, int j, int cnt){
    check[i][j] = true;
    cnt++;
    queue<pair<int,int>> q;
    q.push(make_pair(i,j));
    while(!q.empty()){
        int curI = q.front().first;
        int curJ = q.front().second;
        q.pop();
        //상하좌우 총 4번
        for(int i=0; i<4; i++){
            int valI = curI+low[i];
            int valJ = curJ+col[i];
            if(A[valI][valJ] == 1 && check[valI][valJ] != true){
                q.push(make_pair(valI,valJ));
                check[valI][valJ] = true;
                cnt++;
            }
        }
    }
    return cnt;
    
}
int main()
{
    int N;
    scanf("%d", &N);
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            scanf("%1d", &A[i][j]);
        }
    }
    int elCnt = 0;
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(check[i][j] != true && A[i][j] == 1) {
                int cnt = bfs(i,j,0);
                vectorCnt.push_back(cnt);
                elCnt++;
            }
        }
        
    }
    sort(vectorCnt.begin(), vectorCnt.end());
    cout << elCnt << '\n';
    for(int i=0; i<vectorCnt.size(); i++){
        cout << vectorCnt[i] << '\n';
    }
    return 0;
}