2667)단지 번호 붙이기

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

자료구조나 알고리즘 공부를 똑바로 안해서 자료구조, 알고리즘 활용하는 문제는

피하면서 문제를 푸는데 선택할 수 있는 문제의 폭이 점점 좁아지는 것같다.

특히 3~4문제에 한 문제 꼴로 DP문제가 나오는데 DP 공부를 안해서 DP를 걸렀더니 풀 수 있는 문제가 많지 않다.

이 문제 유형은 세 번째 풀어봐서 어렵지 않게 풀었다.

맵을 입력 받으면 차례로 읽다가 1을 만나면 인접한 영역을 방문하면서 그 수를 세고 방문한 영역을 0으로 만든다.

인접한 영역의 방문이 끝나면 수를 반환한다.

#include<stdio.h>
#define HOME -1
 
void swap(int *A, int *B) {
    int temp;
    temp = *A;
    *A = *B;
    *B = temp;
}
int partition(int *A, int p, int r) {
    int i = p - 1;
 
    for (int j = p; j < r; j++) {
        if (A[j] < A[r]) {
            swap(&A[++i], &A[j]);
        }
    }
    swap(&A[i + 1], &A[r]);
 
    return i + 1;
}
 
void quickSort(int *A, int p, int r) {
    int q;
 
    if (p < r) {
        q = partition(A, p, r);
        quickSort(A, p, q - 1);
        quickSort(A, q + 1, r);
    }
}
int visit(int **map, int n, int i, int j) {
    int count = 0;
 
    if (map[i][j] != HOME) return 0;
    map[i][j] = 0;
 
    if (j + 1 < n) count += visit(map, n, i, j + 1);
    if (i + 1 < n) count += visit(map, n, i + 1, j);
    if (j - 1 >= 0) count += visit(map, n, i, j - 1);
    if (i - 1 >= 0) count += visit(map, n, i - 1, j);
 
    count++;
    return count;
}
 
int main() {
    int n;
    int value;
    char *preMap;
    int **map;
    int count;
    int cntBlock = 0;
    int *cntHome, t = 0;
 
    scanf("%d", &n);
    preMap = (char *)calloc(n + 1, sizeof(char));
    map = (int **)malloc(sizeof(int *)*n);
    for (int i = 0; i < n; i++) {
        map[i] = (int *)calloc(n, sizeof(int));
    }
    cntHome = (int *)calloc(n*n / 2 + 1, sizeof(int));
 
    for (int i = 0; i < n; i++) {
        scanf("%s", preMap);
        for (int j = 0; j < preMap[j] != NULL; j++) {
            if (preMap[j] == '1') map[i][j] = HOME;
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            count = visit(map, n, i, j);
            if (count > 0) {
                cntHome[t++] = count;
                cntBlock++;
            }
        }
    }
 
    quickSort(cntHome, 0, t - 1);
    printf("%d\n", cntBlock);
    for (int i = 0; i < t; i++) {
        printf("%d\n", cntHome[i]);
    }
 
    return 0;
}