5653. 줄기세포배양

5653. 줄기세포배양

아이디어를 캐치하지 못해서 굉장히 헤멘 문제..

일단 처음에 맵의 사이즈를 어느정도로 잡을지도 고민해야했던 문제. 맵의 사이즈는 최대 50x50 이 되고, 그 테두리가 1로 둘러싸여 있을때 

(1일 경우 가장 빨리 먼곳으로 번지므로), 2시간당 1칸씩 늘어나게 되고, 시간은 최대 300이므로, 최대 150까지 사이즈가 늘어난다. 따라서 가

장 많이 줄기세포가 번져도 200x200 안에 들어가게 되므로 그것보다 크게 해주면 된다.

내가 캐치 못한 간단한 '하나의 셀을 두개의 세포가 번식하려고 할때 생명력이 큰 놈이 셀을 차지한다.' 는 부분이었다. 이 부분을 다른 분의 

아이디어를 보고 풀게되었다.

큐를 10개를 사용해서, 가장 큰 생명력을 가진 줄기세포를 먼저 옮기다는 점.

처음에 큐를 한개만 써서, 다양한 조건으로 문제를 풀어봤는데... 잘 안됐다.. 다시 시도해봐야겠다.

while 문을 통해서 시간만큼을 돌게하고, 첫번째 for문에서는 10부터 시작해서 큰 생명력을 가진 큐부터 BFS를 시작한다. 

map[x][y][0] 에는 그 셀의 생명력이 담겨있고, map[x][y][1] 에는 처음 2*생명력이 담겨있고, 시간이 지나면서 줄어든다. 줄어들다가 생명력보

다 작아지면 활성화가 되면서 옆 셀로 번져나간다. 그리고 만약 아직 활성화 중인 상태, map[x][y][1] 이 0보다 크면 활성화 상태이므로, 큐에 

다시 넣는다. map[x][y][0] 이 되면 죽은 세포이므로 아무것도 하지 않는다.

이런식으로 진행하면, 큐안에는 결국 활성화+비활성화된 세포들만 남게 되므로, 큐 10개의 크기를 출력해주면 된다.

<정답 코드>

#include<iostream>
#include<queue>
 
using namespace std;
 
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int map[1000][1000][2];
int dist[1000][1000];
void init()
{
    for (int i = 0; i < 1000; i++)
        for (int j = 0; j < 1000; j++)
        {
            map[i][j][0] = 0;
            map[i][j][1] = 0;
            dist[i][j] = 0;
        }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        init();
        int N, M, K;
        cin >> N >> M >> K;
 
        queue<pair<int,int>> q[11];
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                int tmp;
                cin >> tmp;
                map[500 + i][500 + j][0] = tmp;        //life
                map[500 + i][500 + j][1] = tmp * 2;    //left
 
                if (tmp != 0) {
                    q[tmp].push({ 500 + i,500 + j });
                }
            }
        }
        
        while (K--)
        {
            for (int i = 10; i >= 1; i--)
            {
                int size = q[i].size();
 
                for (int j = 0; j < size; j++)
                {
                    int x = q[i].front().first;
                    int y = q[i].front().second;
                    q[i].pop();
 
                    map[x][y][1]--;
 
                    // 줄기세포가 활성화 될때 퍼져나가기
                    if (map[x][y][0] > map[x][y][1])
                    {
                        for (int d = 0; d < 4; d++)
                        {
                            int nx = x + dx[d];
                            int ny = y + dy[d];
 
                            if (map[nx][ny][0] == 0)
                            {
                                map[nx][ny][0] = map[x][y][0];
                                map[nx][ny][1] = map[x][y][0] * 2;
                                q[i].push({ nx,ny });
                            }
        
                        }
                    }
 
                    // 줄기세포가 활성화 된 상태이면 다시 큐에 넣어줌.
                    if (map[x][y][1] > 0)
                    {
                        q[i].push({ x,y });
                    }
                    
                }
            }
        }
 
        int cnt = 0;
        for (int i = 1; i <= 10; i++)
            cnt += q[i].size();
 
        cout <<"#"<<t<<" "<<cnt << endl;
 
    }
 
    
 
    return 0;
}