5653. [모의 SW 역량테스트] 줄기세포배양

1시간 50분 컷.

제약조건

1. X 시간 동안 비활성화, 활성화 후 X시간 동안 생존

2. 번식 된 후 비활성화 상태.

3. 하나의 셀에는 하나의 세포만 존재.

4. 동시에 번식할 경우 생명력이 큰 세포가 차지.

5. 생명력을 다한 세포는 한 칸을 차지한 상태로 존재.

정답

활성화 + 비활성화 세포의 수

핵심 내용..?

1. 활성화, 비활성화, 죽은 것 판별

2. 한 타임 동안에 활성화 된 세포 번식

접근법

1. 활성화, 비활성화, 죽은 것 판별

ㄱ. 세포 번식을 표시할 배열, 활성화와 비활성화를 판별 할 배열, 같은 시간에 퍼지는지 판단하기 위한 배열 3개를 이용 -> 세포 번식 배열에 새로운 입력이 들어오면 활성화/비활성화 판별 배열에는 생명력*2를 하여 입력.

ㄴ. 활성화/비활성화 판별을 위한 배열은 -1로 초기화. 0은 죽은 것/번식 배열의 값 이하이며 1 이상은 활성화/ 번식 배열의 값 초과는 비활성화 상태.

-> 이 기준을 기반으로 활성화 상태이면, Q에 넣음과 동시에 Q에 들어가는 횟수를 Count. 활성화/비활성화 배열이 1 이상이면 -1씩 해준다.

******************맵의 크기가 무한이라길래 0~1000까지 k번 돌려줬더니...시간 초과가 떳다. 그래서 탐색하는 X,Y의 최대 최소를 계속 갱신해주면서 Q에 넣어주며, 활성화/비활성화 배열의 -1씩 해주기 위해 탐색하는 범위를 제한해주었다.

2. 한 타임 동안에 활성화 된 세포 번식

*Q에 들어가는 횟수만큼 BFS를 돌려준다. 이때, 아무 세포도 존재하지 않거나, 퍼져나갈 곳에 이미 세포가 있으면 생명력이 더 크고 같은 시간에 퍼졌는지를 판별 후 퍼트릴지 말지를 결정한다.

설명하기 어렵다.

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x;
}point;
 
int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
int map[1000][1000], sepo[1000][1000], round[1000][1000];
int sepo_count, N, M, K, Q_Front, Q_Back, Cnt, MAX_X, MAX_Y, MIN_X, MIN_Y;
point Q[1000 * 1000];
int main()
{
    int Test_num;
    scanf("%d", &Test_num);
 
    for (int T = 1; T <= Test_num; T++)
    {
        sepo_count = 0;
        Q_Back = -1;
        Q_Front = -1;
        memset(map, 0, sizeof(map));
        memset(sepo, -1, sizeof(sepo));
        memset(Q, 0, sizeof(Q));
        memset(round, -1, sizeof(round));
        scanf("%d %d %d", &N, &M, &K);
 
        MIN_X = 450;
        MIN_Y = 450;
        MAX_X = 450 + M;
        MAX_Y = 450 + N;
 
        for (int i = 450; i < 450 + N; i++)
        {
            for (int j = 450; j < 450 + M; j++)
            {
                scanf("%d", &map[i][j]);
 
                if (map[i][j] != 0)
                {
                    sepo[i][j] = 2 * map[i][j];
                    round[i][j] = 0;
                }
            }
        }
 
        int y = 0, x = 0, yy = 0, xx = 0;
 
        //생명력 감소
        for (int i = MIN_Y; i < MAX_Y; i++)
        {
            for (int j = MIN_X; j < MAX_X; j++)
            {
                if (sepo[i][j] > 0)
                {
                    sepo[i][j]--;
                }
            }
        }
 
        for(int k = 1 ; k < K ; k++)
        {
            Cnt = 0;
            //활성화 후, 번식할 세포 count
            for (int i = MIN_Y; i <= MAX_Y; i++)
            {
                for (int j = MIN_X; j <= MAX_X; j++)
                {
                    if ((map[i][j] >= sepo[i][j]) && sepo[i][j] > 0)
                    {
                        Q[++Q_Back].y = i;
                        Q[Q_Back].x = j;
                        Cnt++;
                    }
                    //생명력 감소
                    if (sepo[i][j] > 0)
                    {
                        sepo[i][j]--;
                    }
                }
            }
 
            //번식
            for (int i = 0; i < Cnt; i++)
            {
                y = Q[++Q_Front].y;
                x = Q[Q_Front].x;
 
                for (int j = 0; j < 4; j++)
                {
                    yy = y + dy[j];
                    xx = x + dx[j];
 
                    if ((map[yy][xx] == 0 && sepo[yy][xx] == -1) || ((map[y][x] > map[yy][xx]) && (k == round[yy][xx])))
                    {
                        round[yy][xx] = k;
                        map[yy][xx] = map[y][x];
                        sepo[yy][xx] = 2 * map[y][x];
 
                        if (xx < MIN_X)
                            MIN_X = xx;
                        if (xx > MAX_X)
                            MAX_X = xx;
                        if (yy < MIN_Y)
                            MIN_Y = yy;
                        if (yy > MAX_Y)
                            MAX_Y = yy;
                    }
                }
            }
        }
 
        for (int i = 0; i < 1000; i++)
        {
            for (int j = 0; j < 1000; j++)
            {
                if (sepo[i][j] > 0)
                {
                    sepo_count++;
                }
            }
        }
 
        printf("#%d %d\n", T, sepo_count);
    }
 
    return 0;
}