Softeer [level 2] : 장애물 인식 프로그램 (C 언어)

https://softeer.ai/practice/info.do?idx=1&eid=409&sw_prbl_sbms_sn=170703 

Softeer

Code:

#include <stdio.h>
#include <stdlib.h>
 
int arr[26][26] = { 0, };
int cnt = 0;
int temp[26*26] = { 0, };
int count = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int n;
 
void dfs(int i, int j)
{
    arr[i][j] = 0;
    cnt++;
    for (int k = 0; k < 4; k++)
    {
        int y = i + dy[k];
        int x = j + dx[k];
        if (y >= 0 && y < n && x >= 0 && x < n && arr[y][x] == 1)
        {
            dfs(y, x);
        }
    }
}
 
int compare(const void* a, const void* b)
{
    if (*(int*)a > *(int*)b) return 1;
    else if (*(int*)a < *(int*)b) return -1;
    else return 0;
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%1d", &arr[i][j]);
        }
    }
    int a = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] == 1)
            {
                cnt = 0;
                dfs(i,j);
                temp[a++] = cnt;
                count++;
            }
        }
    }
    qsort(temp, count, sizeof(int), compare);
    printf("%d\n", count);
    for (int i = 0; i < count; i++)
    {
        printf("%d\n", temp[i]);
    }
}
 

문제풀이:

1. 배열을 입력을 %1d로 받는다.(다 붙어있으므로)

2. dfs를 이용해서 인접한 1의 개수를 check하여 temp배열에 저장한다.

3. qsort를 이용해 정렬한다.