5653.줄기세포배양

이번에 풀어볼 문제는 SW Expert의 줄기세포 배양이다.

SW Expert Academy

이 문제에서는 배울게 정말 많았던거 같다. 내용은 그렇게 어렵지않다. 그냥 문제에서 시키는대로 하면된다.

문제는 그 설계가 생각보다 복잡하다는 것이다. 

결국 다른사람의 코드를 보고 이해하면서 배우는 선택을 했다.. 후..;; ( 참고 : https://it-earth.tistory.com/51 )

이 분의 풀이법을 보면 굉장히 체계적으로 딱딱 맞아떨어진다고 생각한다.

vector를 구조체를 이용해서 정확하게 문제에서 필요한 요구조건들을 확인해간다.

무엇보다 탐색기준을 시간을 잡는 건 생각을 못했던거 같다... 그래도 배웠으니까 긍정적으로 생각해야겠다.

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
 
#include <iostream>
#include <vector>
 
#define MAX 400
 
using namespace std;
 
int T, N, M, K;
struct cell{
    int x;
    int y;
    int life;
    int flow;
    int status;
    bool work;
};
 
vector<cell>cells, birth, alive;
int maxlife[MAX][MAX];
int status[MAX][MAX]; // 1:비활 2:활 3:다이
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
void reset(){ //사용 배열 초기화
    for (int i = 0; i < MAX; i++){
        for (int j = 0; j < MAX; j++){
            maxlife[i][j] = status[i][j] = 0;
        }
    }
}
int search(){
    for (int time = 1; time <= K; time++){ // 시간을 기준으로 진행
        for (int i = 0; i < cells.size(); i++){ // 배양한 세포의 좌표만을 이용하기위해 size
            if (cells[i].status != 3){    // 죽은세포가 아니라면
                if (cells[i].status == 1){// 그중 비활성화된 세포면
                    if (time == cells[i].flow){ // 이세포가 시간에 흐름에 따라 생명과 같아지면
                        cells[i].status = 2;  // 상태를 활성화로 바꿔주고
                        status[cells[i].x][cells[i].y] = 2; // 상태 배열도 활성화로 나타내준다.
                        cells[i].flow = time + cells[i].life; // 생명력만큼 시간이 흘렀고 그 시간을 활성화한 이후부터 더해주어야 생명력만큼 활성화할 수 있다.
                    }
                }
                else if (cells[i].status == 2){ // 활성화된 세포라면
                    if (cells[i].work==true){  // 번식이 가능한지 확인하고 가능하다면
                        for (int z = 0; z < 4; z++){ // 퍼진다.
                            int ax = cells[i].x + dx[z];
                            int ay = cells[i].y + dy[z];
                            if (status[ax][ay] == 0){ //주변에 배양공간이 있는것이 발견된다면
                                if (maxlife[ax][ay] < cells[i].life){ // 그 공간에 발견된 곳이 최대생명력보다 배양할 세포의 생명력이 크다면
                                    birth.push_back({ ax, ay, cells[i].life, time + cells[i].life, 1, true }); // 새로운 새포 배양
                                    status[ax][ay] = 1; // 상태를 비활성화로 배양
                                    maxlife[ax][ay] = cells[i].life; // 최대크기의값을 갱신
                                }
                            }
                        }
                        cells[i].work = false; // 배양이 끝났으므로 기존세포는 1시간만 배양가능하기 때문에 번식력을 잃음
                    }
                    if (time == cells[i].flow){ // 활성화상태가 된 이후로 진행한시간이 생명력과 같아지면 세포는 죽음
                        status[cells[i].x][cells[i].y] = 3; // 죽은 세포 표시
                        cells[i].status = 3; // 해당 세포의 상태도 죽음으로 표시
                    }
                }
            }
        }
        for (int t = 0; t < cells.size(); t++){ 
            if (cells[t].status != 3){ // 죽은 세포들이 아닌 것들은
                alive.push_back(cells[t]); // 살아있는 세포에 저장
            }
        }
        cells.clear(); // 세포상태를 비움
        for (int t = 0; t < birth.size(); t++){ // 새로태어난 세포들중에
            alive.push_back(birth[t]); // 살아있는 세포에 저장
        }
        for (int t = 0; t < alive.size(); t++){ // 살아있는 세포들을 모아서
            cells.push_back(alive[t]); // 탐색을위해 저장
        }
        alive.clear(); // 살아있는세포들을 다음 탐색을 위해 비움
        birth.clear(); // 새로태어난 새포들도 다음 탐색을 위해 비움
    }
    return (int)cells.size(); // 마지막에 있는 죽은세포외의 모든 세포들 리턴
}
 
int main() {
    freopen("5653.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        reset(); //새로운 테스트케이스를 위한 초기화
        cells.clear(); // 세포정보도 초기화
        cin >> N >> M >> K;
        int life;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < M; j++){
                cin >> life;
                if (life){
                    cells.push_back({ i + 150, j + 150, life, life, 1, true }); //최대300이므로 150정도로 잡음
                    status[150 + i][150 + j] = 1; // 해당 값의 시작점들은 비활성상태로 시작
                }
            }
        }
        cout << "#" << z << " " << search() << "\n"; // 탐색진행
    }
    return 0;
}