[SWEA] 줄기세포배양

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo

SW Expert Academy

[풀이]

 

•     입력 : 각 세포의 생명력

•     생명력의 수치 x라고 할 때 x시간동안 비활성 상태이고 x시간이 지나는 순간 활성화된다.

•     활성화상태가 되면 x시간동안 살아있으며 x시간이 지나면 죽는다. (죽은 상태에서도 셀을 차지한다. )

•     활성화된 줄기세포는 첫 1시간동안 상하좌우로 번식을 한다. 번식된 세포는 처음에는 비활성화 상태이다.

•     하나의 그리드셀에는 한의 세포만 존재할 수 있다.-> 두 개이상의 세포가 동시에 번식하려고 할 경우

•     생명력수치가 높은 줄기세포가 차지한다.

•     용기는 무한한 수치이다. => N = 50 / M = 50 이므로 1001으로 잡아도 된다.

•     K <= 300 이고 n, m <= 50 이므로 150씩 더하여 위치를 정해준다. (경계값에 걸리지 않도록)

 

 

* 증식은 활성화된 세포만 가능하다. (enable == true 조건을 필요)

* 세포 증식은 첫 1시간만 한다. => 새로 증식된 세포를 넣을 때 age를 -1로 하는 이유 

 

---

 

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
 
#define INF 1001
 
using namespace std;
 
//줄기세포 배양 -BFS
/*
    입력 : 각 세포의 생명력 
    생명력의 수치 x라고 할 때 x시간동안 비활성 상태이고 x시간이 지나는 순간 활성화된다. 
    활성화상태가 되면 x시간동안 살아있으며 x시간이 지나면 죽는다. (죽은 상태에서도 셀을 차지한다. )
    활성화된 줄기세포는 첫 1시간동안 상하좌우로 번식을 한다. 번식된 세포는 처음에는 비활성화 상태이다. 
    하나의 그리드셀에는 한의 세포만 존재할 수 있다.-> 두 개이상의 세포가 동시에 번식하려고 할 경우 
    생명력수치가 높은 줄기세포가 차지하낟. 
    용기는 무한한 수치이다. => N = 50 / M = 50 이므로 1001으로 잡아도 된다. 
    k= 300 이고 n = 50 m = 50 이므로 150씩 더하여 위치를 정해준다. (경계값에 걸리지 않도록)
 */
int cells[INF][INF];
int n, m, k; //세로 가로 배양시간
 
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
 
typedef struct Cell
{
    int x;
    int y;
    int life; //생명력
    bool enable;
    int time; //현재 시간과 동일할 경우 활성화 결정
    int age;  //누적 시간
 
    Cell() {}
    Cell(int _x, int _y, int _l, bool _e, int _t, int _a) : x(_x), y(_y), life(_l), enable(_e), time(_t), age(_a) {}
} Cell;
 
queue<Cell> q;
 
void bfs()
{
    int cur_time = 0;
    while (cur_time < k)
    {
        //k시간동안 배양
 
        //활성화 비활성화 판단 / 사망 진단
        while (1)
        {
            if (q.front().time == cur_time)
            {
                Cell now = q.front();
                q.pop();
 
                if (!now.enable)
                {
                    //활성화
                    now.time++;
                    now.age++;
 
                    if (now.age == now.life)
                        now.enable = true;
 
                    q.push(now);
                }
 
                else
                {
                    now.time++;
                    now.age++;
 
                    //사망진단 (세포는 life시간동안 비활성화 + 활성화 + 증식(1시간) => 죽음 )
                    //초기에 age 를 -1로 넣는 이유는 증식하는데 1시간을 쓰기 때문.
                    if (now.life * 2 != now.age)
                    {
                        q.push(now);
                    }
                }
            }
            else
                break;
        } //while (1)
 
        vector<Cell> newCells;
 
        //증식
        int size = q.size();
 
        for (int i = 0; i < size; i++)
        {
            Cell now = q.front();
            q.pop();
 
            if (now.enable)
            {
                int x = now.x;
                int y = now.y;
 
                for (int j = 0; j < 4; j++)
                {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
 
                    if (nx < 0 || nx >= INF || ny < 0 || ny >= INF)
                        continue;
 
                    Cell nc(nx, ny, now.life, false, now.time, -1);
 
                    if (cells[nx][ny] == 0)
                    {
                        //세포 증식 가능 셀
                        newCells.push_back(nc);
                        cells[nx][ny] = 2;
                    }
                    else if (cells[nx][ny] == 2)
                    {
                        //새로 증식한 셀인데 동시에 다른 세포가 증식할 경우
                        int list_size = newCells.size();
                        for (int z = 0; z < list_size; z++)
                        {
                            if (newCells.at(z).x == nx && newCells.at(z).y == y && newCells.at(z).life < now.life)
                            {
                                //생명력이 더 큰 Now 셀이 증식함
                                newCells.erase(newCells.begin() + z);
                                newCells.push_back(nc);
                                break; //더 살펴볼 필요 없음
                            }
                        }
                    }
                } //for direction
            }
            q.push(now); //다시 큐에 넣어준다.
        }                 //for q
 
        //새로 증식한 셀들을 큐에 넣어준다.
        for (Cell tmp : newCells)
        {
            cells[tmp.x][tmp.y] = 1; //이제 정식 셀이니 1로 만들어준다.
            q.push(tmp);
        }
        cur_time++;
    }
}
 
void init()
{
    memset(cells, 0, sizeof(cells));
}
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++)
    {
        cin >> n >> m >> k;
 
        init();
 
        int life;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> life;
 
                if (life > 0)
                {
                    //q add
                    Cell c(i + 150, j + 150, life, false, 0, 0);
                    cells[i + 150][j + 150] = 1;
                    //세포가 존재함 (0 : 세포 없음 / 2 : 증식된 세포 )
                    q.push(c);
                }
            }
        }
        //입력
 
        bfs();
        //탐색
 
        int ans = 0;
        while (!q.empty())
        {
            Cell now = q.front();
            q.pop();
 
            if (now.age >= 0)
            {
                ans++;
            }
        }
        cout << "#" << tc << " " << ans << '\n';
    }
 
    return 0;
}