[SWEA] 5653. 줄기세포배양

▶문제설명

[SWEA] 5653. 줄기세포배양

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

▶Hint

---

입력으로 주어지는 K의 최대값이 300이므로

세포의 생명력이 모두 1이라고 가정했을 때 상하좌우 최대 150개씩 번식해 나갈 수 있다.

입력으로 주어지는 세포의 정보를 저장할 2차원 배열을 하나 만들고

좌표의 시작값을 한 가운데로 하여 세포의 생명력 값을 입력받는다.

[각 세포가 가지는 정보]

1. 비활성/활성/죽음을 나타내는 상태 정보

2. 생명력

3. 좌표

4. 번식의 여부

5. 상태가 변화할 다음 시간에 대한 정보

시간이 흐름에 따라 각 세포들의 상태에 따라

현재 상태가 비활성인 경우와 활성인 경우로 나누어 작업을 수행한다.

번식할 때 생명력이 다른 세포가 겹칠 때 생명력이 큰 세포가 우선이 되어야 하므로

그것을 판단하기 위한 2차원 배열을 관리하여 해결한다.

▶Solution

---

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
 
int N, M, K;
int status[400][400]; // 1:비활성, 2:활성, 3:죽음
int maxLife[400][400]; // 생명력이 큰 것을 우선하기 위함
int dr[4] = { 0,0,-1,1 };
int dc[4] = { -1,1,0,0 };
 
typedef struct Cell {
    int r, c, life, changetime, status;
    bool first;
}Cell;
 
vector<Cell> cells, birth, alive;
 
void input() {
    scanf("%d %d %d", &N, &M, &K);
 
    cells.clear();
    for (int i = 0; i < 400; i++) {
        for (int j = 0; j < 400; j++) {
            status[i][j] = 0;
            maxLife[i][j] = 0;
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int life;
            scanf("%d", &life);
            if (life != 0) {
                cells.push_back({ 150 + i,150 + j,life,life,1,true });
                status[150 + i][150 + j] = 1;
            }
        }
    }
}
 
int solve() {
    for (int time = 1; time <= K; time++) 
    {
        for (int i = 0; i < cells.size(); i++) {
            if (cells[i].status != 3) {
 
                if (cells[i].status == 1) { // 비활성
                    if (time == cells[i].changetime) {
                        cells[i].status = 2;
                        status[cells[i].r][cells[i].c] = 2;
                        cells[i].changetime = time + cells[i].life;
                    }
                }
 
                else if (cells[i].status == 2) { // 활성
                    if (cells[i].first == true) {//활성상태 첫 한시간
                        //번식
                        for (int p = 0; p < 4; p++) {
                            int R, C;
                            R = cells[i].r + dr[p];
                            C = cells[i].c + dc[p];
 
                            if (status[R][C] == 0 ) {
                                if (maxLife[R][C] < cells[i].life) {
                                    birth.push_back({ R, C, cells[i].life,time+cells[i].life, 1, true });
                                    status[R][C] = 1;
                                    maxLife[R][C] = cells[i].life;
                                }
                            }
                        }
                        cells[i].first = false;
                    }
 
                    if (time == cells[i].changetime) {
                        cells[i].status = 3;
                        status[cells[i].r][cells[i].c] = 3;
                    }
                }
            }
        }
 
        for (int j = 0; j < cells.size(); j++) {
            if (cells[j].status != 3)
                alive.push_back(cells[j]);
        }
        for (int j = 0; j < birth.size(); j++) {
            if (birth[j].life == maxLife[birth[j].r][birth[j].c]) {
                alive.push_back(birth[j]);
            }
        }
 
        cells.clear();
        for (int j = 0; j < alive.size(); j++) {
            cells.push_back(alive[j]);
        }
 
        alive.clear();
        birth.clear();
    }
 
    return (int)cells.size();
}
 
int main() {
    int T, answer;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        
        input();
 
        answer = solve();
 
        printf("#%d %d\n", t, answer);
    }
    return 0;
}