소프티어

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>


struct road {
    bool checked; // 확인 했는지 여부
    char block; // 블록의 형태(장애물인지)
    short obstacle; // 장애물 블록 번호
};


struct node {
    char x;
    char y;
    struct node *next;
};


struct queue {
    struct node *first;
    struct node *last;
};


void init_head(struct queue *head)
{
    head->first = NULL;
    head->last = NULL;
}


bool is_empty(struct queue *head)
{
    if (head->first == NULL && head->last == NULL)
        return true;
    else
        return false;
}


void insert(struct queue *head, struct node *data)
{
    if (is_empty(head)) {
        head->first = data;
        head->last = data;
        data->next = NULL;
    } else {
        head->last->next = data;
        head->last = data;
        data->next = NULL;
    }
}


struct node *delete(struct queue *head)
{
    struct node *tmp = NULL;
    if (!is_empty(head)) {
        if (head->first == head->last) {
            tmp = head->first;
            head->first = NULL;
            head->last = NULL;
        } else {
            tmp = head->first;
            head->first = head->first->next;
        }


        return tmp;
    }
    return NULL;
}


void bfs(
    struct queue *head,
    struct road **st,
    int len,
    int n,
    int m,
    int block_num
)
{
    struct node *tmp = (struct node *)malloc(sizeof(struct node));
    int x, y;
    tmp->x = n;
    tmp->y = m;


    insert(head, tmp);


    while(!is_empty(head)) {
        struct node *data = delete(head);
        struct node *new_data = NULL;
        if (data != NULL) {
            x = data->x;
            y = data->y;
            if (len > y + 1 && !st[x][y + 1].checked && st[x][y + 1].block == 1) {
                st[x][y + 1].checked = true;
                st[x][y + 1].obstacle = block_num;
                new_data = (struct node *)malloc(sizeof(struct node));
                new_data->x = x;
                new_data->y = y + 1;


                insert(head, new_data);
            }


            if (len > x + 1 && !st[x + 1][y].checked && st[x + 1][y].block == 1) {
                st[x + 1][y].checked = true;
                st[x + 1][y].obstacle = block_num;
                new_data = (struct node *)malloc(sizeof(struct node));
                new_data->x = x + 1;
                new_data->y = y;


                insert(head, new_data);
            }


            if (0 <= x - 1 && !st[x - 1][y].checked && st[x - 1][y].block == 1) {
                st[x - 1][y].checked = true;
                st[x - 1][y].obstacle = block_num;
                new_data = (struct node *)malloc(sizeof(struct node));
                new_data->x = x - 1;
                new_data->y = y;


                insert(head, new_data);
            }


            if (0 <= y - 1 && !st[x][y - 1].checked && st[x][y - 1].block == 1) {
                st[x][y - 1].checked = true;
                st[x][y - 1].obstacle = block_num;
                new_data = (struct node *)malloc(sizeof(struct node));
                new_data->x = x;
                new_data->y = y - 1;


                insert(head, new_data);
            }


            free(data);
        }
    }
}


int search(struct road **st, int len, struct queue *head)
{
    int block_num = 1;
    for (int i=0; i<len; i++) {
        for (int j=0; j<len; j++) {
            if (!st[i][j].checked &&
                st[i][j].block == 1) {
                st[i][j].checked = true;
                st[i][j].obstacle = block_num;
                bfs(head, st, len, i, j, block_num);
                block_num++;
            }
        }
    }


    return block_num;
}


int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}


int main(void)
{
    int N, block_num;
    int *arr;
    char *str;
    struct road **st = NULL;
    struct queue q_head;
    scanf("%d", &N);


    str = (char *)malloc(N + 1);
    st = (struct road **)malloc(sizeof(struct road *) * N);
    for (int i=0; i<N; i++) {
        st[i] = (struct road *)malloc(sizeof(struct road) * N);
        scanf("%s", str);
        for (int j=0; j<N; j++) {
            st[i][j].checked = false;
            st[i][j].obstacle = 0;
            st[i][j].block = str[j] - '0';
        }
    }


    init_head(&q_head);
    block_num = search(st, N, &q_head);
    printf("%d\n", block_num - 1);


    if (block_num == 1) {
        printf("0");
        return 0;
    }
    
    arr = (int *)malloc(sizeof(int) * block_num);
    memset(arr, 0, sizeof(int) * block_num);
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            arr[st[i][j].obstacle]++;


    qsort(arr+1, block_num-1, sizeof(int), compare);
    for (int i=1; i<block_num; i++) {
        if (i == block_num-1)
            printf("%d", arr[i]);
        else
            printf("%d\n", arr[i]);
    }
    return 0;
}

정말 무식하게 풀었네요..