SWEA5653.md

줄기세포배양

https://swexpertacademy.com/main/main.do [5653] 줄기세포배양

개요

N*M(1<=N,M<=50)의 맵에 줄기세포(X=1~10)들이 주어진다. 줄기세포들은 (X+1)~(2*X-1)시간에 사방으로 번식하고 2*X시간에 죽어 자리를 차지한다. 만약 줄기세포들이 같은 자리에 번식할 경우 X가 높은 줄기세포가 번식되게 된다. 배양시간 K(1<=K<=300)시간 후에 살아있는 줄기세포들을 구하는 문제

분석

시간 복잡도

T*N*M 이기때문에 시간 내에 출력될 수 있다.

알고리즘

1. Map[450][450], julgi[5000][4], julgi2[5000][4] // julgi(x, y, X, t) - 좌표, X값, 태어난 이후부터 지난시간 t

2. scanf(“%d”, &map[i+200][j+200] // 맵의 최대크기제한은 없으나 X=1인 줄기세포인 경우 300시간동안 양쪽으로 150만큼 늘어나게 된다. 따라서 200의 여유를 둠.

3. julgi[++ct][0]~[3](x, y, X, t)에 줄기세포 값을 저장해주고 map[i+200][j+200]!=0 이면 –1로 갱신한다.

4. T만큼 반복

   1. julgi[i][3]++
   2. julgi[i][3]이 X보다 크고 2*X보다 작은 julgi[i]+4방향의 좌표를 map[julgi[i][0]+4방향][julgi[i][1]+4방향]로 검사하며 –1이 아닌 경우에 최댓값(julgi[i][2])을 갱신한다.
   3. julgi[i][3]이 2*X보다 작으면 julgi2에 넣는다. julgi[i]+4방향의 좌표를 한번더 검사하며 –1이 아닌 경우 최댓값과 같은 julgi[i][2]를 갖는 julgi[i]를 julgi2에 넣고(julgi[i][3]=0) map의 값을 –1로 갱신한다.
   4. julgi2를 julgi에 복사한다.

5. 결과 출력

기타

map을 탐색하며 값이 있는 부분을 살핀다면 450*450*K의 시간복잡도(본인기준 시간초과)가 필요하지만 번식할 줄기세포만을 따로 저장하여 탐색한다면 더 적은 연산을 할 수 있다. 기존에 있던 미생물들을 map에 –1체크를 해주며 새로운 미생물들을 큐에 넣는 것이 좋은 방법이었다고 생각한다.

소스

#include <stdio.h>
 
int bang[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int map[450][450], sefo[5000][4], sefo2[5000][4], N, M, K;
 
int main()
{
    int T, i, j, k, l, sn, ct,x, y;
    scanf("%d", &T);
    for (i = 1; i <= T; i++)
    {
        scanf("%d%d%d", &N, &M, &K);
        sn = 0;
 
        for (j = 0; j < 450; j++)
        {
            for (k = 0; k < 450; k++)
            {
                map[j][k] = 0;
            }
        }
 
        for (j = 0; j < N; j++)
        {
            for (k = 0; k < M; k++)
            {
                scanf("%d", &map[j+200][k+200]);
                if (map[j+200][k+200] != 0)
                {
                    sefo[++sn][0] = j+200;
                    sefo[sn][1] = k+200;
                    sefo[sn][2] = map[j+200][k+200];
                    sefo[sn][3] = 0;
                    map[j+200][k+200] = -1;
                }
            }
        }
 
        for (j = 1; j <= K; j++)
        {
            ct = 0;
            for (k = 1; k <= sn; k++)
            {
                if (sefo[k][2] <= sefo[k][3] && sefo[k][3] < (sefo[k][2] * 2))
                {
                    for (l = 0; l < 4; l++)
                    {
                        x = sefo[k][0] + bang[l][0];
                        y = sefo[k][1] + bang[l][1];
                        if (map[x][y] != -1 && map[x][y] < sefo[k][2])
                        {
                            map[x][y] = sefo[k][2];
                        }
                    }
                }
                sefo[k][3]++;
            }
            for (k = 1; k <= sn; k++)
            {
                if (sefo[k][3] < (sefo[k][2] * 2))
                {
                    sefo2[++ct][0] = sefo[k][0];
                    sefo2[ct][1] = sefo[k][1];
                    sefo2[ct][2] = sefo[k][2];
                    sefo2[ct][3] = sefo[k][3];
                }
                for (l = 0; l < 4; l++)
                {
                    x = sefo[k][0] + bang[l][0];
                    y = sefo[k][1] + bang[l][1];
                    if (map[x][y] == sefo[k][2])
                    {
                        sefo2[++ct][0] = x;
                        sefo2[ct][1] = y;
                        sefo2[ct][2] = map[x][y];
                        sefo2[ct][3] = 0;
                        map[x][y] = -1;
                    }
                }
            }
 
            sn = ct;
            for (k = 1; k <= sn; k++)
            {
                for(l=0; l<4; l++) sefo[k][l] = sefo2[k][l];
            }
        }
 
        printf("#%d %d\n", i, sn);
    }
 
}