[알고리즘] 백준 2667번: 단지번호붙이기 (c언어)

출처: https://www.acmicpc.net/problem/2667

 

출처: https://www.acmicpc.net/problem/2667

 

이 문제는 dfs방식을 이용해서 풀었다. 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

char graph[25][25];
int house[625] = { 0, };
int sorted[625];


int dfs(int i, int j, int n, int cnt)
{
	//한번 집이 있는 것(1)을 확인했다면 0으로 바꾸어주기
    graph[i][j] = 0;
    //하나의 단지에 있는 집의 개수 세기
    house[cnt]++;

	//좌우 위아래로 집이 있으면 같은 단지이기 때문에 재귀로 dfs호출
    if (i - 1 >= 0 && graph[i - 1][j] == '1') 
        dfs(i - 1, j, n, cnt);
    if (i + 1 < n && graph[i + 1][j] == '1')
        dfs(i + 1, j, n, cnt);
    if (j - 1 >= 0 && graph[i][j - 1] == '1')
        dfs(i, j - 1, n, cnt);
    if (j + 1 < n && graph[i][j + 1] == '1')
        dfs(i, j + 1, n, cnt);

	//좌우 위아래로 집이 더이상 없으면 재귀함수 종료
    return 0;
}

//합병정렬
void merge(int list[], int left, int mid, int right) {
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    while (i <= mid && j <= right) {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }

    if (i > mid) {
        for (l = j; l <= right; l++)
            sorted[k++] = list[l];
    }
    else {
        for (l = i; l <= mid; l++)
            sorted[k++] = list[l];
    }

    for (l = left; l <= right; l++) {
        list[l] = sorted[l];
    }
}

void merge_sort(int list[], int left, int right) {
    int mid;

    if (left < right) {
        mid = (left + right) / 2; 
        merge_sort(list, left, mid); 
        merge_sort(list, mid + 1, right); 
        merge(list, left, mid, right); 
    }
}

int main() {   
    int n;
    int cnt = 0;

    //지도 크기 입력받기
    scanf("%d", &n);
    //집이 있는지(1) 없는지(0) 입력받기
    for (int i = 0; i < n; i++)
    {
        scanf("%s", graph[i]);
    }

	//지도를 돌면서 집이 있으면(1) dfs로 지도 순회하기
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (graph[i][j] == '1')
            {
                dfs(i, j, n, cnt);
                //단지 개수 세기
                cnt++;
            }
        }
    }

    printf("%d\n", cnt);

	//오름차순으로 집 개수 정렬
    merge_sort(house, 0, cnt - 1);
    for (int i = 0; i < cnt; i++)
        printf("%d\n", house[i]);

    return 0;
}