[SW Expert 5653] 줄기세포배양

#문제

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

#풀이

큐를 사용하여 매시간마다 세포들을 체크하며 배양해 나아갔다.

첫번째 난관은 배열의 크기를 정하는 것이었다.

해당 문제에서 배열의 최대 크기를 정해주지 않았기 때문에 알아서 만들어야한다.

세포의 경우 초기 위치가 최대 크기가 50X50 이란 것을 주었고, 시간이 최대 300이란 것이 주어졌으므로 배열의 최대 크기를 구할 수는 있다.

일단 50X50크기의 배열에 생명이 1인 세포들이 전체 있다고 했을때, 세포들은 활성화 시간에 번식을 한다.

따라서, 2초에 크기는 1씩 커지는 셈이다.

그렇기에 최대로 커질 수 있는 높이는 150 + 50 + 150 (위,아래 모두 진행 되기때문)가 된다.

좌우도 높이와 똑같기 때문에 크기가 350인 이차원 배열을 만들어 사용하였다.

각 입력에 대해여 칸마다 세포들의 상태, 생명, 비활성화 시간, 활성화 시간을 주었다.

만약 0인 입력일 때는 세포가 없으므로 상태를 -1로 주었다.

각 시간마다, 세포들의 상태에 따라 비활성화 시간 또는 활성화 시간을 하나씩 줄인다.

그 후에 활성화 된 세포가 있다면 큐에 추가시킨다.

이를 모든 칸에 대하여 돈 뒤, 활성화 된 세포들을 번식 시킨다.

번식 시킬 때는 해당 위치의 세포가 있는지 없는지를 검사하고 없을경우(-1)일 때는 현재 세포의 정보를 복사하여 해당 칸에 넣어준다.

이때, 비활성화 시간과 활성화 시간은 생명으로 넣어주어야 된다.(새로운 세포이기 때문)

만약 번식 위치에 다른 세포가 있는데 그 세포도 막 생겨난 경우 즉, 상태가 0이며 해당 세포의 생명과 비활성화 시간이 같은 경우에는 번식할 세포의 생명력과 이미 있는 세포의 생명력을 비교한 뒤에 큰 세포를 해당 칸에 넣어준다.

이후에 계속해서 시간을 늘리며, 원하는 시간 K 직전까지 돌린다.

이유는 위에서 미리 시간을 줄이기 때문이다.

#코드

#include <iostream>
#include <queue>
using namespace std;
 
int N,M,K;
struct Cell{
    int state = -1;
    int life;
    int unActiveTime;
    int activeTime;
};
Cell box[350][350];
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
int main(){
    int tc;
    cin >> tc;
    for(int t = 1; t <= tc; t++){
        Cell initCell;
        initCell.state = -1;
        initCell.life = 0;
        initCell.unActiveTime = 0;
        initCell.activeTime = 0;
        for(int i = 0; i < 350; i++){
            for(int j = 0; j < 350; j++){
                box[i][j] = initCell;
            }
        }
        cin >> N >> M >> K;
        for(int r = 0; r < N; r++){
            for(int c = 0; c < M; c++){
                int life;
                cin >> life;
                if(life > 0){
                    Cell cell;
                    cell.life = life;
                    cell.unActiveTime = life;
                    cell.activeTime = life;
                    cell.state = 0;
                    box[r+150][c+150] = cell;
                }
            }
        }
        int time = 0;
        while(time < K){
            queue<pair<int, int>> activeCells;
            for(int r = 0; r < 350; r++){
                for(int c = 0; c < 350; c++){
                    if(box[r][c].state == 0){
                        if(box[r][c].unActiveTime > 0){
                            box[r][c].unActiveTime--;
                        }
                        if(box[r][c].unActiveTime == 0){
                            box[r][c].state = 1;
                        }
                    }else if(box[r][c].state == 1){
                        if(box[r][c].activeTime > 0){
                            activeCells.push({r,c});
                            box[r][c].activeTime--;
                        }
                        if(box[r][c].activeTime == 0){
                            box[r][c].state = 2;
                        }
                    }
                }
            }
            while(!activeCells.empty()){
                int r = activeCells.front().first;
                int c = activeCells.front().second;
                activeCells.pop();
                for(int i = 0; i < 4; i++){
                    int nr = r + dr[i];
                    int nc = c + dc[i];
                    if(nr < 0 || nr >= 350 || nc < 0 || nc >= 350) continue;
                    if(box[nr][nc].state < 0){
                        box[nr][nc].state = 0;
                        box[nr][nc].life = box[r][c].life;
                        box[nr][nc].unActiveTime = box[r][c].life;
                        box[nr][nc].activeTime = box[r][c].life;
                    }else if(box[nr][nc].state == 0 && box[nr][nc].life == box[nr][nc].unActiveTime){
                        if(box[nr][nc].life < box[r][c].life){
                            box[nr][nc].life = box[r][c].life;
                            box[nr][nc].unActiveTime = box[r][c].life;
                            box[nr][nc].activeTime = box[r][c].life;
                        }
                    }
                }
            }
            time++;
        }
        int ans = 0;
        for(int i = 0; i < 350; i++){
            for(int j = 0; j < 350; j++){
                if(box[i][j].state == 0 || box[i][j].state == 1)
                    ans++;
            }
        }
        cout << "#"<< t << " " <<ans << endl;
    }
    return 0;
}