1012)유기농 배추

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

이 문제를 어떻게 간단하게 볼 수 있을까?

지렁이는 네 방향으로만 움직일 수 있다.

어떤 특정한 지점에서 네 방향으로만 움직이면서 지나갔던 자리에 표시해두자.

이렇게 만들어진 다각형을 4방향 채움 다각형이라 한다.

왼쪽 그림처럼 4방향으로 이동하면서 색을 채운 다각형의 모습은 오른쪽 그림과 같다.

지렁이는 동서남북 네 방향으로만 이동하기 때문에 위 다각형의 각 셀을 모두 방문할 수 있다.

만약 위처럼 두 영역이 인접해 있는 경우에 지렁이는 인접한 영역으로 이동할 수 있을까?

지렁이는 대각선 방향의 이동을 할 수 없기 때문에 인접한 영역으로 이동할 수 없다.

따라서 위 영역에서 지렁이는 두 마리가 필요하다고 볼 수 있다.

문제를 조금 더 쉽게 표현하면 4방향 채움 다각형의 수가 몇 개인지를 찾는 것과 같다.

 

위 그림에서 4방향 채움 다각형의 수는 몇 개인가? 총 6개이다.

그렇다면 위와 같은 다각형의 수를 어떻게 세야할까?

아래의 알고리즘은 4방향 채움 알고리즘이고 재귀 호출을 통해 인접영역을 같은 색으로 채운다.

void fillArea(int i,int j){
    if() return; //경계 조건
    else{
        //do anything
    }
    fillArea(i,j+1);
    fillArea(i-1,j);
    fillArea(i,j-1);
    fillArea(i+1,j);
}

위 알고리즘을 약간 변형해 4방향 채움 다각형을 없앨 것이다.(왜..?)

나는 이 문제를 다음과 같은 방법으로 해결했다.

우선 주어진 행렬을 차례로 탐색한다.(초기 행렬은 0으로 초기화되어 있고 영역에 해당하는 원소는 1을 저장하고 있음)

1을 만나면 그 시점에서 변형된 fillArea()를 수행한다.(변형된 fillArea()를 uncheckArea()라 부르겠음)

uncheckArea()는 경계 조건에 걸리지 않는다면 방문한 원소를 0으로 만든다.

uncheckArea()에 진입시 경계 조건에 걸렸다면 0을 반환한다.

uncheckArea()가 끝나면 1을 반환한다.(채움 다각형이 1개 있음을 뜻함)

uncheckArea()가 반환한 값을 카운팅한다.

예를 들어보자.

초기 행렬이 다음 그림과 같이 주어졌다.

이 행렬에 차례로 접근할 때 언젠가 1을 만날 것이다.

1을 만나면 uncheckArea()를 호출한다.

uncheckArea()는 4방향으로 만들어지는 영역을 모두 0으로 만들고 지운 영역의 수 1을 반환한다.

위와 같은 과정을 반복한다.

코드는 아래와 같다.

#include<stdio.h>
#define CHECK 1
#define UNCHECK 0
 
void showArea(int **tempArea,int M, int N) {
    for (int i = 0; i < M;i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", tempArea[i][j]);
        }
        printf("\n");
    }
}
 
int uncheckArea(int **tempArea, int M, int N, int i,int j) {
    if (!(i >= 0 && i < M) || !(j >= 0 && j < N)) return 0;
    if (tempArea[i][j]==UNCHECK) return 0;
    else {
        tempArea[i][j] = UNCHECK;
    }
    uncheckArea(tempArea, M, N, i,j+1);
    uncheckArea(tempArea, M, N, i+1,j);
    uncheckArea(tempArea, M, N, i,j-1);
    uncheckArea(tempArea, M, N, i-1,j);
    
    return 1;
}
 
int **allocMatrix(int M,int N,int K) {
    int **totalArea;
    int x, y;
 
    totalArea = (int **)malloc(sizeof(int *)*M);
    for (int i = 0; i < M; i++) {
        totalArea[i] = (int *)calloc(sizeof(int), N);
    }
    for (int i = 0; i < K; i++) {
        scanf("%d %d", &x, &y);
        totalArea[x][y] = CHECK;
    }
    return totalArea;
}
 
int main() {
    int num;
    int M, N;
    int K;
    int **totalArea;
    int count = 0;
 
    scanf("%d",&num);
    for (int i = 0; i < num;i++) {
        scanf("%d %d %d", &M, &N, &K);
        totalArea = allocMatrix(M,N,K);
        //showArea(totalArea, M, N);
 
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                count += uncheckArea(totalArea, M, N, i, j);
            }
        }
        printf("%d\n", count);
        count = 0;
        free(totalArea);
    }
 
    return 0;
}