2583)영역 구하기

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

흰 배추벌레 문제랑 비슷하다.

주어진 입력을 처리하는 방법부터 생각해보자.

직사각형의 영역을 입력할 때 왼쪽 아래가 시작점이고 오른쪽 위가 끝나는 점이다.

이 점들은 아래 그림처럼 x,y 좌표계의 좌표다. 

전체 영역에서 어떤 영역의 면적을 표현하기 위해 2차원 배열을 사용할텐데

2차원 배열은 아래 그림처럼 i,j의 증가 방향이 x,y 좌표계와 일치하지 않는다는 점을 유의해야 한다.

이 문제는 연속하는 흰색 영역의 갯수와 그 크기를 출력하는 문제다.

위 그림에서 흰색 영역의 갯수는 3개이고 각각의 크기는 1, 7, 13이다.

연속하는 영역의 크기를 구하기 위해 재귀적으로 4방향 탐색 방법을 사용할 것이다.

특정 영역의 면적은 TRUE로 표현했고 그렇지 않은 영역은 FALSE로 표현했다.

재귀 알고리즘이 최초로 배열의 각 요소에 접근할 때 FALSE인 경우에 TRUE로 바꿔주고 count를 하나 늘려준다.

현재 요소를 기준으로 오른쪽,아래쪽,왼쪽,위쪽 방향으로 배열의 요소에 접근하는 것이 유효한지 검사하고

유효하면 그 요소를 방문하고 방문이 끝나고 반환한 결과를 count에 합산한다.

각 요소 방문이 끝나면 count를 리턴한다.

#include<stdio.h>
#define TRUE 1
#define FALSE 0
 
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 visitArea(int **area, int R, int C, int x,int y) {
    int count = 0;
    if (area[x][y] == TRUE) return 0;
 
    area[x][y] = TRUE;
    count += 1;
 
    if (y+1<C) count += visitArea(area, R, C, x, y+1);
    if (x+1<R) count += visitArea(area, R, C, x+1, y);
    if (y-1>=0) count += visitArea(area, R, C, x, y-1);
    if (x-1>=0) count +=visitArea(area, R, C, x-1, y);
 
    return count;
}
 
int main() {
    int m, n, k;
    int **area;
    int *areaScale;
    int x0, y0, x1, y1;
    int count = 0;
    int t = 0;
    
    scanf("%d %d %d",&m,&n,&k);
    area = (int **)malloc(sizeof(int *)*m);
    areaScale = (int **)calloc(m*n/2+1,sizeof(int));
 
    for (int i = 0; i < n;i++) {
        area[i] = (int *)calloc(n, sizeof(int));
    }
 
    for (int c = 0; c < k;c++) {
        scanf("%d %d %d %d",&x0,&y0, &x1,&y1);
        for (int i = y0; i < y1;i++ ) {
            for (int j = x0; j < x1;j++) {
                area[(m-1)-i][j] = TRUE;
            }
        }
    }
 
    for (int i = 0; i < m;i++) {
        for (int j = 0; j < n;j++) {
            count = visitArea(area, m, n, i, j);
            if (count != 0) {
                areaScale[t++] = count;
                count = 0;
            }
        }
    }
 
    quickSort(areaScale, 0, t-1);
    printf("%d\n",t);
    for (int i = 0; i < t;i++) {
        printf("%d ", areaScale[i]);
    }
    printf("\n");
 
    return 0;
}