5212)지구 온난화

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

문제를 단순화 해보면 'X'에 인접한 '.'가 3개 이상이면 'X'를 '.'로 바꿔 주는 게 전부이다.

여기서 인접해있다는 말은 대각선 방향이 아닌 네 방향으로 인접한 것을 뜻한다.

그림처럼 'X'를 기준으로 상하좌우만 고려했을 때 모두 '.'이기 때문에 X를 '.'으로 바꿔줘야 한다. 

다른 문제를 생각해보자. 만약 'X'가 경계나 모서리에 위치해있을 때 어떻게 인접한 '.'를 세어야 할까?

그림에서 표시된 'X'는 모두 배열 경계 바깥 쪽에 '.'이 있는 것으로 간주하고 '.'의 수를 세어야 한다.

왜냐하면 주어진 입력은 최소 크기의 섬이 있는 지도이기 때문이다. 지도 바깥은 모두 바다라고 간주해야 한다.

'X'가 배열의 경계에 위치할 때 찾아볼 수 있는 특징은 i=0 이거나 i= R-1 또는 j=0이거나 j=C-1이다.(R:행의 크기,C:열의 크기)

'X'가 위와 같은 경우 중 하나일 때 '.' 수를 하나 세어주면 된다.

이렇게 50년 뒤에 바다에 잠길 섬을 찾아낸 후에 다시 섬의 분포에 딱 맞게 지도의 크기를 줄여야 한다.

원래 지도의 크기가 5x5였고 'X'를 '.'으로 바꿔준 결과가 위 그림과 같다고 하자.

위 그림에서 빨강색 박스만큼 지도를 줄여야 한다.

지도 크기를 줄일 때 오른쪽 최상단의 'X'와 왼쪽 최하단의 'X'가 지도의 크기를 결정한다.

공교롭게도 오른쪽 최상단 'X'는 'X'중에서 가장 작은 i와 가장 큰 j를 갖고

왼쪽 최하단 'X'는 'X'중에서 가장 큰 i와 가장 작은 j를 갖는다.

이 값들을 알아내면 mini부터 maxi까지, minj부터 maxj까지 지도를 출력해주면 된다.

#include<stdio.h>
#define MAX(A,B) (A>B)?A:B
#define MIN(A,B) (A<B)?A:B
 
int adjencyCount(char **map,int R,int C,int i,int j) {
    int count = 0;
 
    if (i == 0) count++;
    if (i == R-1) count++;
    if (j == 0) count++;
    if (j == C-1) count++;
 
    if(i-1>=0 && map[i-1][j] == '.') count++;
    if(i+1<R && map[i+1][j] == '.') count++;
    if(j-1>=0 && map[i][j-1] == '.') count++;
    if(j+1<C && map[i][j+1] == '.') count++;
    
    return count;
}
 
int main() {
    int R, C;
    char **map;
    char **after;
    int maxi = -1, maxj = -1;
    int mini, minj;
 
    scanf("%d %d",&R,&C);
    mini = R, minj = C;
 
    map = (char **)malloc(sizeof(char *)*R);
    for (int i = 0; i < R;i++) {
        map[i] = (char *)malloc(sizeof(char)*(C + 1));
    }
    after = (char **)malloc(sizeof(char *)*R);
    for (int i = 0; i < R; i++) {
        after[i] = (char *)calloc(C+1,sizeof(char));
    }
 
    for (int i = 0; i < R;i++) {
        scanf("%s",map[i]);
    }
    for (int i = 0; i < R;i++) {
        for (int j = 0; map[i][j] != NULL;j++) {
            if (map[i][j] == 'X') {
                if (adjencyCount(map, R, C, i, j) >= 3) after[i][j] = '.';
                else {
                    maxi = MAX(i, maxi), minj = MIN(j, minj);
                    mini = MIN(i, mini), maxj = MAX(j, maxj);
                    after[i][j] = 'X';
                }
            }
            else after[i][j] = '.';
        }
    }
 
    for (int i = mini; i <= maxi; i++) {
        for (int j = minj; j <= maxj;j++) {
            printf("%c",after[i][j]);
        }
        printf("\n");
    }
 
    return 0;
}