[2667] 단지번호붙이기

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

2667번: 단지번호붙이기

<문제>

문제의 <그림1>의 형태로 입력이 주어지면, <그림2>의 형태로 변환하는 문제로 볼 수 있는데

더 어려운 문제의 경우 이를 묵시적으로 요구하는 경우가 종종 있다.

 

입력되는 맵의 좌상단부터 우하단까지 순회하며 '1'인 정점을 시작으로 bfs를 돌린다.

<그림2>처럼 그대로 구현해도 되지만, "이미 탐색된 1번단지"와 "아직 탐색하지 않은 집"인지 구분이 안되니

애초에 단지의 번호를 2부터 시작하도록 구현해도 된다.

나중에 번호를 사용할때에 -1만 해주면 2부터 시작해도 무방하기 때문에, 2부터 시작하도록 배열을 하나만 선언했다.

 

<소스코드>

#include <stdio.h>
 
#include <algorithm>
#include <queue>
using namespace std;
queue<int> q;
int a[26][26], n, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int f(int sy, int sx, int k) {
    int i, y, x, ty, tx, cnt;
    q.push(sy);
    q.push(sx);
    a[sy][sx] = k;
    cnt = 1;
    while (!q.empty()) {
        ty = q.front();
        q.pop();
        tx = q.front();
        q.pop();
        for (i = 0; i <= 3; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (x >= 0 && y >= 0 && x < n && y < n && a[y][x] == 1) {
                q.push(y);
                q.push(x);
                a[y][x] = k;
                cnt++;
            }
        }
    }
    return cnt;
}
int main(void) {
    int i, j, key, cnt, num[1000] = {0};
    char s[26][26] = {0};
    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%s", &s[i]);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (s[i][j] == '1') a[i][j] = 1;
    key = 2;
    cnt = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (a[i][j] == 1) {
                num[cnt] = f(i, j, key);
                key++;
                cnt++;
            }
        }
    }
    sort(num, num + cnt);
    printf("%d\n", cnt);
    for (i = 0; i < cnt; i++) printf("%d\n", num[i]);
    return 0;
}