[dovelet][DFS] 단지 번호 붙이기 / danji

dovelet    16 단계 DFS

단지 번호 붙이기 / danji

http://59.23.113.171/30stair/danji/danji.php?pname=danji

#include <stdio.h>
 
int map[50][50];
int danji[50][50];
int total = 1;
int count[50];
 
void dfs(int i, int j)
{
    map[i][j] = 0;
    danji[i][j] = total;
    count[total]++;
 
    if (map[i - 1][j] < 0)    dfs(i - 1, j);
    if (map[i][j - 1] < 0)    dfs(i, j - 1);
    if (map[i + 1][j] < 0)    dfs(i + 1, j);
    if (map[i][j + 1] < 0)    dfs(i, j + 1);
 
    return;
}
 
void sort(void)
{
    int i, j, temp1, temp2;
 
    for (i = 1; count[i] != 0; i++)    {
        j = 1;
        if (count[i] < count[i - 1])    {
            
            while (count[j] < count[i]) j++;
 
            temp1 = count[i];
            for (; j <= i; j++)    {
                temp2 = count[j];
                count[j] = temp1;
                temp1 = temp2;
            }
        }
    }
 
    return;
}
 
int main(void)
{
    int n, i, j, temp;
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++)    {
        for (j = 1; j <= n; j++)    {
            scanf("%d", &temp);
            
            if (temp == 1)        {
                map[i][j] = -1;
            }
        }
    }
 
    for (i = 1; i <= n; i++)    {
        for (j = 1; j <= n; j++)    {
            if (map[i][j] < 0)    {
                dfs(i, j);
                total++;
            }
        }
    }
 
    sort();
 
    printf("%d\n", total - 1);
 
    for (i = 1; i < total; i++)    {
        printf("%d\n", count[i]);
    }
    return 0;
}

 

 sort 를 직접 구현

개수를 세어서 배열에 넣고 sort 하는 거 말고

count한 거를 sort하면서 배열에 넣을 수도 있을 듯