백준 - 단지번호붙이기 : 2667번

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

2667번: 단지번호붙이기

플러드 필 문제중 한개이다.

 

연결요소 문제와 유사하게 방문하지 않은 정점을 찾아서 dfs / bfs 순회를 해주면 된다.

 

여기서 정점의 정보는 [행,열]이 된다. 즉, (x,y)값을 한개의 정점으로 생각하면 됨.

 

그리고 이런 문제에서는 인접 정점을 찾는 방법은 아래와 같이 한개 정점 (x,y)에서 위/아래/좌/우로 이동을 위해 변경되야할 좌표값을 아래 배열과 같이 넣어두고 for문을 돌리면 간단하게 구현 할 수 있다.

 

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

 

연속된 숫자중 1개 자리씩만 입력을 받고 싶을경우 아래 코드를 이용하면 된다.

scanf("%1d", &input[i][j]);

 

 

아래 소스코드는 bfs를 사용해서 해결하였다.

 

#include <bits/stdc++.h>
using namespace std;

int input[30][30];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int n;
int res[25 * 25];
#define Dangi_Start_Num 2  //플러드 필에 사용되는 단지 시작 번호
void bfs(int x, int y, int cnt) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    input[x][y] = cnt;

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {  //input 배열의 범위밖을 참조하지 않도록 하기 위해
                if (input[nx][ny] == 1) {
                    q.push(make_pair(nx, ny));
                    input[nx][ny] = cnt;
                }
            }
        }
    }
}
int main() {

    //지도 정보 입력 받기
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &input[i][j]);
        }
    }
    //플러드 필
    int cnt = Dangi_Start_Num;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (input[i][j] == 1) {
                bfs(i, j, cnt++);
            }
        }
    }
    //단지 개수 출력
    printf("%d\n", cnt - Dangi_Start_Num);
    
    //플러드 필된 값(즉, 단지번호) 별로 몇개가 있는지 개수를 셈
    //그 개수를 res배열에 index는 단지배열이고, 그곳에 그 단지의 개수를 저장해둠.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (input[i][j] != 0)
                res[input[i][j] - Dangi_Start_Num] += 1;
        }
    }
    //res를 오른 차순으로 정렬함.
    sort(res, res + cnt - Dangi_Start_Num);
    //단지별 개수를 오름차순으로 출력함.
    for (int i = 0; i < cnt - Dangi_Start_Num; i++) {
        printf("%d\n", res[i]);
    }

    return 0;
}