SWEA 5653 [모의 SW 역량테스트] 줄기세포배양 C++

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

SW Expert Academy

 

최종 코드

• GitHub github.com/hwayeon351/SWEA-Algorithms

hwayeon351/SWEA-Algorithms

//
//  main.cpp
//  SWEA5653
//
//  Created by Hwayeon on 2021/01/23.
//
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct cell{
    int x;
    int y;
    int power;
    int timer;
};

struct greater_p{
    bool operator()(cell c1, cell c2){
        return c1.power < c2.power;
    }
};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main(int argc, char** argv)
{
    int test_case;
    int T;
    int N, M, K;
    int num_dead, num_alive;
    vector<cell> cells;

    cin>>T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        int cont[400][400] = {0,};
        priority_queue<cell, vector<cell>, greater_p> active_cell;
        cin >> N >> M >> K;
        cells.clear();
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                int c_power;
                cin >> c_power;
                cont[200+i][200+j] = c_power;
                if(c_power > 0){
                    cells.push_back({200+j, 200+i, c_power, c_power});
                }
            }
        }
        
        num_alive = cells.size();
        num_dead = 0;
        int time = 0;
        while(time < K){
            time++;
            for(int i=0; i<num_alive; i++){
                cells[i].timer--;
                if(cells[i].timer == -1) active_cell.push(cells[i]);
                if(cells[i].timer == -cells[i].power) num_dead++;
            }
            while(!active_cell.empty()){
                cell now_cell = active_cell.top();
                for(int i=0; i<4; i++){
                    int nx = now_cell.x + dx[i];
                    int ny = now_cell.y + dy[i];
                    if(cont[ny][nx] == 0){
                        num_alive ++;
                        cont[ny][nx] = now_cell.power;
                        cells.push_back({nx, ny, now_cell.power, now_cell.power});
                    }
                }
                active_cell.pop();
            }
        }
        cout << "#" << test_case << " " << num_alive - num_dead << endl;
    }
    return 0;
}

 

 

---

풀이 과정

풀이 시간  3시간

 이 문제의 핵심은 세포의 생명력 수치에 따라 비활성 상태와 활성 상태의 지속시간이 달라진다는 것이다.

따라서, 생명력 수치의 크기 순으로 세포를 담을 수 있도록 priority_queue(우선 순위 큐)라는 자료구조를 활용해야한다.

이전에 나는 priority_queue의 존재를 몰랐었기 때문에, 이를 따로 코드로 구현하면서 애 먹었다. 그래서 나는 다른 사람의 코드를 참고해서 문제를 해결했다.

다른 사람의 코드를 보면서 이 문제는 priority_queue를 활용하면 효율적이라는 것을 알았고, 코드를 보면서 priority_queue 활용 방법을 익혔다.

만약, 나처럼 priority_queue에 대해 모르고 있었다면 아래 priority_queue에 관해 정리한 포스팅이 있으니 먼저 보고 오면 좋겠다.

 

 그렇다면, priority_queue를 활용하여 문제를 풀어보도록 하자.

 

1. priority_queue<cell, vector<cell>, greater_p> active_cell, vector<cell> cells 선언하기

 벡터 cells에는 비활성화 상태의 세포들을 담아주고, active_cell에는 활성화 되어 번식이 시작되는 세포들을 담아줄 것이다. 

struct cell{
    int x;
    int y;
    int power;
    int timer;
};

struct greater_p{
    bool operator()(cell c1, cell c2){
        return c1.power < c2.power;
    }
};

vector<cell> cells;
priority_queue<cell, vector<cell>, greater_p> active_cell;

먼저, cell과 greater_p라는 구조체를 선언하자.

cell은 세포의 위치를 담아 줄 x, y와 생명력인 power, 세포의 상태를 변경해주는 시점을 알려주거나 비활성화 및 활성화 상태가 얼마나 지속되었는지를 나타내는 timer로 구성되어 있다.

grater_p는 연산자 오버로딩을 통해 두 세포의 생명력을 비교해 c1.power < c2.power이 참이면 true, 아니면 false을 반환하도록 하였다.

그리고 cell 자료형을 갖는 cells 벡터와 greater_p를 정렬 기준으로 삼은 active_cell 우선 순위 큐를 선언해준다.

 

 

2. 배양 용기 설정 및 cells 초기화

 두 번째로, 세포를 배양 시킬 용기를 설정해줘야 한다. 이때, 주의해야할 점은 문제의 제약 사항을 보면 배양 용기의 크기가 무한하다는 점이다. 즉, 세포가 번식할 수 있는 상태라면 용기의 크기와 상관 없이 계속 증식이 가능하다는 것이다.

그동안 접해왔던 문제는 배열의 크기에 제약이 있어서 초기화 할 때 최대 크기의 경우를 반영했었다. 하지만 이 문제에서는 배양 용기를 다르게 설정해주어야 한다.

 

여기에서 힌트를 얻을 수 있는 점은 초기 상태에서 줄기 세포가 분포된 영역이 1≤N≤50, 1≤M≤50 라는 점과 배양 시간 K는 300 이하의 정수라는 점이다. 줄기 세포는 생명력 수치만큼의 시간 동안 비활성 상태이고 그 후 바로 활성 상태로 바뀌어 또 다시 생명력 수치만큼의 시간동안 활성 상태가 된다. 활성 상태에는 상, 하, 좌, 우로 1씩 번식이 이뤄진다. 따라서, 최대치인  K=300, N=50, M=50이라고 가정해보면, 50X50 배양 용기에서 상, 하, 좌, 우로 150씩 번식한다는 것을 알 수 있다.

 

 즉, 배양 용기의 크기를 350X350 언저리로 지정하면 된다! 나는 여유있게 400X400으로 설정해 문제를 풀었다.

int cont[400][400] = {0,};

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                int c_power;
                cin >> c_power;
                cont[200+i][200+j] = c_power;
                if(c_power > 0){
                    cells.push_back({200+j, 200+i, c_power, c_power});
                }
            }
        }

for문을 통해 초기 상태에서 줄기 세포의 생명력을 받아 배양 용기 cont에 담아준다. 이 때, 배양 용기의 중앙 쯤에 위치하도록 cont[200][200]부터 담아주었다.(문제에서 배양 용기 가장자리에 닿아서 번식할 수 없는 경우는 없다고 되어있기 때문)

또한, 생명력이 0보다 큰 경우 cells에 x = 200+j, y = 200+i, power = c_power, timer = c_power로 하여 푸쉬한다. timer를 생명력으로 초기화 한 이유는 앞서 말했듯이 생명력만큼의 시간만큼 비활성 상태가 유지되고 바로 활성 상태로 바뀌어 유지되기 때문이다. 

 

 

3. 줄기 세포 배양

 세팅이 되었으니 이제 줄기 세포를 배양해보자.

	num_alive = cells.size();
        num_dead = 0;
        int time = 0;
        while(time < K){
            time++;
            for(int i=0; i<num_alive; i++){
                cells[i].timer--;
                if(cells[i].timer == -1) active_cell.push(cells[i]);
                if(cells[i].timer == -cells[i].power) num_dead++;
            }
            while(!active_cell.empty()){
                cell now_cell = active_cell.top();
                for(int i=0; i<4; i++){
                    int nx = now_cell.x + dx[i];
                    int ny = now_cell.y + dy[i];
                    if(cont[ny][nx] == 0){
                        num_alive ++;
                        cont[ny][nx] = now_cell.power;
                        cells.push_back({nx, ny, now_cell.power, now_cell.power});
                    }
                }
                active_cell.pop();
            }
        }

num_alive는 살아있는 세포의 수, num_dead는 죽은 세포의 수를 나타내는 변수이다. 앞서 초기 세포를 cells에 담았기 때문에 num_alive = cells.size()로 초기화 하고, num_dead = 0으로 초기화 해준다.

또한, time은 경과 시간을 의미하고 0으로 초기화 한다.

 

 이제, while문을 통해 경과 시간이 배양 시간이 될 때 까지 배양을 하도록 한다.

 

1) 경과 시간을 업데이트 한다. time++

2) for문을 통해 cells에 담긴 모든 세포들의 timer를 가동시킨다. cells[i].timer--

1.  cells[i].timer == -1인 경우, 활성화 상태로 전환 되므로 active_cell에 해당 세포를 push 해준다.
2. cells[i].timer == -cells[i].power인 경우, 세포는 죽게되므로 num_dead를 카운팅한다.

 예를 들어, 생명력이 4인 초기 상태의 세포가 cells에 있다고 하면, 경과 시간이 3일 때까지는 비활성화 상태였다가 4시간 째에 바로 활성화 되고, 번식은 그로부터 한 시간 뒤 부터 진행될 것이다. 이에 따라, timer == 0일 때는 세포가 활성화 되는 타이밍, 그로부터 한 시간 뒤로 timer == -1이 되면 그 때 상, 하, 좌, 우로 번식이 시작된다. 그래서 세포가 timer == -1일 때 active_cell에 해당 세포를 push 해준다.

 timer == -1 일 때부터 번식이 시작 되었으니, timer == -4 일 때 세포가 죽게 된다. 따라서, cells[i].timer == -cells[i].power일 때 num_dead를 카운팅 해 주는 것이다.

 

3) active_cell.empty() 일 때까지 번식을 진행한다.

1. active_cell.top()을 now_cell에 담아준다.
2. now_cell로 부터 배양 용기 상, 하, 좌, 우에 세포가 없는 경우, 세포를 번식한다. 이 때, num_alive++을 하고, 해당 위치 cont[ny][nx]에 now_cell.power을 담아준다. 또한, cells.push({nx, ny, now_cell.power, now_cell.power})를 통해 새 세포를 cells에 담아준다.
3. now_cell의 번식이 종료되었으므로 active_cell.pop() 한다.

여기에서, active_cell은 우선 순위 큐로 greater_p에 따라 생명력이 큰 거부터 정렬이 되므로 생명력이 큰 거부터 번식을 함으로써, 문제에서 요구하는 생명력 수치가 높은 줄기 세포가 그리드 셀을 차지하도록 하였다. 이 점이 우선 순위 큐 priority_queue를 사용하는 핵심 이유이다.

 

4) 위의 1), 2), 3)을 반복하여 경과 시간 time == K가 되어 바깥 while문에서 빠져나오면, num_alive - num_dead를 하여 최종 살아있는 줄기 세포의 개수(비활성 상태 + 활성 상태)를 출력한다.

 

 

---

참고

• 2021/02/02 - [C++] - [STL] Priority Queue

[STL] Priority Queue