[영상처리 스터디] Queue를 이용해 문제를 풀어보자.

오늘 풀 문제는 바로 단지번호붙이기이다. 이 문제에 대해 이미 올렸었는데 이 글은 여기와 또 다른 소스코드가 있다. 거기에서도 C로 queue를 구현했지만 너무 못짰다............ 거기는 C로 구현한거 빼고 보는걸 추천한다.

설명은 거기서 했었으니 바로 소스코드만 올리겠다. (간단한 설명을 보고 싶은 사람은 여기에 가서 읽고 오면 된다.)

#include<stdio.h>
#include<stdlib.h>
 
struct pos
{
    int y;
    int x;
};
 
struct queue
{
    struct queue *next;
    struct pos POS;
};
 
typedef struct queue Queue;
 
typedef struct
{
    Queue* head;
    Queue* tail;
    int size;
}qq;
 
typedef qq* Q;
 
void init(Q q)
{
    q->head = (Queue*)malloc(sizeof(Queue));
    q->head->next = NULL;
    q->tail = q->head;
    q->size = 0;
    return;
}
 
void push(Q q, int y, int x)
{
    Queue *New = (Queue*)malloc(sizeof(Queue));
    New->next = NULL;
    q->tail->POS.y = y;
    q->tail->POS.x = x;
    q->tail->next = New;
    q->tail = New;
    q->size++;
}
 
void pop(Q q)
{
    Queue *del = q->head;
    q->head = q->head->next;
    free(del);
    q->size--;
}
 
struct pos front(Q q)
{
    return q->head->POS;
}
 
int IsEmpty(Q q)
{
    return !q->size; // return q->size == 0;
    //return q->head == q->tail;
}
 
int map[30][30];
int output[1000];
int pointer = 0; 
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
int main()
{
    Q q = (Q)malloc(sizeof(qq));
    init(q);
 
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%1d", &map[i][j]);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            if (map[i][j])
            {
                int count = 0;
                push(q,i,j);//y == i, x == j
                map[i][j] = 0;
 
                while (!IsEmpty(q))
                {
                    ++count;
                    struct pos now = front(q); pop(q);
 
                    for (int k = 0; k < 4; k++)
                    {
                        int qy = now.y + dy[k];
                        int qx = now.x + dx[k];
 
                        if (0 > qy || qy >= n || 0 > qx || qx >= n)continue;
 
                        if (map[qy][qx])
                        {
                            map[qy][qx] = 0;
                            push(q, qy,qx);
                        }
                    }
                }
                output[pointer++] = count;
            }
        }
 
    int temp;
    for (int i = 0; i < pointer - 1; i++)
    {
        for (int j = i + 1; j < pointer; j++)
        {
            if (output[i] > output[j])
            {
                temp = output[i];
                output[i] = output[j];
                output[j] = temp;
            }
        }
    }
 
    printf("%d\n", pointer);
 
    for (int i = 0; i < pointer; i++)
        printf("%d\n", output[i]);
 
    return 0;
}