BOJ 2667번 : 단지번호붙이기

2차원 배열에서 연결되어있는 숫자 1 끼리의 묶음을 찾는 문제이다.

연결되어있는 숫자들을 찾기 위해서는 BFS 또는 DFS를 사용한다.

이 문제의 경우에는 묶음의 갯수와 각 묶음안의 원소 갯수를 찾는 문제이다.

 

<Solution>

이렇게 입력이 붙어있을 경우에는 getchar()를 사용하면 편리하다.

하지만 getchar의 경우 엔터를 입력으로 인식하기 때문에 버퍼에 엔터가 남아있어 입력시 원하는대로 동작하지 않을 수 도 있다. 이를 위해 엔터가 들어가는 부분마다 getchar를 넣어줘야 한다.

 

2차원 배열에서 연결된 묶을을 찾기 위해서는, 이전 글에서 사용한 DFS와 비슷하지만, 체크해서 넘어가야 하는 방향이 위,아래,오른쪽,왼쪽으로 4방향이다.

if 문을 사용하여 모든 방향을 고려해야 한다.

 

이런 경우에는 경계 부분을 처리하기 곤란할 수도 있겠지만, 우리가 사용하는 배열보다 2씩 크게 만들어 0으로 채우면, 원소가 존재하는지 체크할때 알아서 넘어가게 하면 쉽게 구현이 가능하다.

 

main문에서 배열의 모든 부분들을 체크하고, 2차원 배열에서 원소가 존재할 때만 dfs로 넘기고, dfs를 실행하는 함수에서 방문체크 배열을 조작하여 main문에서 체크하는 부분을 넘어가게 만들면 구현이 쉽다.

 

<소스코드>

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
 
int chk[27][27] = { 0, };
int arr[27][27] = { 0, };
int n;
vector<int> cnt; // 각 묶음의 원소 갯수 저장하는 벡터
 
void dfs(int y, int x) {
    chk[y][x] = 1;                       // 방문 체크
    cnt[cnt.size() - 1]++;               // 각 묶음 안의 원소 갯수 ++
 
    if (!chk[y - 1][x] && arr[y - 1][x]) // 위
        dfs(y-1, x);    
    if (!chk[y + 1][x] && arr[y + 1][x]) // 아래
        dfs(y + 1, x);
    if (!chk[y][x + 1] && arr[y][x + 1]) // 오른
        dfs(y, x + 1);
    if (!chk[y][x - 1] && arr[y][x - 1]) // 왼
        dfs(y, x - 1);
}
 
void Solve() {
    memset(chk, 2, sizeof(chk));
    cin >> n;
    getchar();
    for (int i = 1; i <=n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] = getchar() - '0';
            chk[i][j] = 0;
        }
        getchar();
    }
    for (int i = 1; i <= n; i++) { 
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] && !chk[i][j]) { //전체 돌면서 방문 안했고, 어레이에 남아있는부분 찾아서 dfs
                cnt.push_back(0);
                dfs(i, j);
            }
        }
    }
    cout << cnt.size()<<endl;
    sort(cnt.begin(), cnt.end());
    for (int i = 0; i < cnt.size(); i++)
        cout << cnt[i] << endl;
}
 
int main() {
    Solve();
}
 

 

<문제>

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

2667번: 단지번호붙이기