[백준 2667] 단지번호붙이기 [C]

백준 - 2667

---

풀이

단지별로 bfs를 사용해 탐색하고, 방문한 곳을 0으로 만들어주었다. 

단지내 집의 수를 main으로 반환해 complex에 담아주었고, Quick Sort로 정렬 후 출력해주었다.

---

소스코드

#include <stdio.h>
#include <stdlib.h>
#define MAX 25
typedef struct{
    int x, y;
}Point;

Point queue[MAX*MAX];
int graph[MAX][MAX], rear, N;
int dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1};

int compare(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
void push(int i, int j){
    queue[rear].x = i;
    queue[rear++].y = j;
}
int bfs(int x, int y){
    int area = 1, front = 0;
    graph[x][y] = 0, rear = 0;
    push(x, y);
    while (front != rear){
        x = queue[front].x;
        y = queue[front++].y;
		
        for (int dir = 0; dir < 4; dir++){
            int tx = x + dx[dir], ty = y + dy[dir];
			
            if (tx >= 0 && ty >= 0 && tx < N && ty < N)
                if (graph[tx][ty]){
                    graph[tx][ty] = 0;
                    push(tx, ty);
                    area++;
                }
        }
    }
    return area;
}
int main(){
    scanf("%d", &N);
    for (int i = 0; i < N*N; i++)
        scanf("%1d", &graph[i/N][i%N]);
		
    int cnt = 0, complex[N*N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (graph[i][j])
                complex[cnt++] = bfs(i, j);
    
    qsort(complex, cnt, sizeof(int), compare);
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++)
        printf("%d\n", complex[i]);
}

---

출처

2667번: 단지번호붙이기