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

문제

SWEA 모의 SW 역량테스트 - 5653 줄기세포배양

SW Expert Academy

 

---

문제 풀이

접근 방식

K시간 후 살아있는 줄기 세포의 총개수를 구하는 문제이다.

 

이를 구하기 위해 우선 cell이라는 구조체를 만들어서 위치(x, y)와 생명력 수치(X),

현재 남은 생명력 수치(t)를 저장해주었다.

struct cell {
    int x;
    int y;
    int X;
    int t;
};

 

그리고 배양 시간의 최댓값은 300 시간이고, 배양 용기의 초기 크기는 최대 50 × 50이다.

즉, 생명력 수치가 1인 세포가 번식하는 데 걸리는 시간은 총 2시간으로,

300시간 동안에는 상하좌우로 150만큼 번식한다.

그래서 실제 배양 용기(map)의 크기는 무한이지만 최대 350만큼 커지기 때문에350 × 350 크기로 설정해주었고,

(150, 150)의 위치에서 초기 배양 용기를 저장하도록 설정해주었다.

 

입력받을 때에 값이 0이 아닌 경우는 줄기 세포이기 때문에 이들을 큐에 저장해주었다.

그 후, K시간 동안 while문을 수행하며 BFS 방식으로 세포를 배양해주었다.

 

비활성화에서 활성화가 되는 시간은 t가  0이 되었을 때지만, 그다음 시간에 번식을 하기 때문에

-1이 되었을 때 번식을 하도록 구현하였다. 번식할 세포들은 우선순위 큐에 넣어서

생명력 수치가 큰 세포부터 번식을 하도록 설정해주었고, 번식할 때마다 len을 증가시켜주었다.

 

활성화된 세포가 죽는 시간은 -(생명력 수치) 시간일 때이다.

그래서 그 시간이 된 세포가 있을 때마다 dead를 증가시켜주었다.

 

마지막으로 K시간이 지난 후 살아있는 세포의 수인 len - dead를 출력해주었다.

 

---

풀이 코드 - C++

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
 
using namespace std;
 
struct cell {
    int x;
    int y;
    int X;
    int t;
};
 
struct cmp {
    bool operator()(cell a, cell b) {
        return a.X < b.X;
    }
};
 
int main(int argc, char** argv) {
    int test_case, i, j, a, dead, len, x, y, X, nx, ny;
    int T, N, M, K;
    int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
    int map[350][350];
    vector<cell> cells;
    priority_queue<cell, vector<cell>, cmp> activation;
 
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> N >> M >> K;
        memset(map, 0, sizeof(map));
        cells.clear();
        for (i = 0; i < N; i++) {
            for (j = 0; j < M; j++)  {
                cin >> a;
                map[150+i][150+j] = a;
                if(a != 0)
                    cells.push_back({ 150 + i, 150 + j, a, a });
            }
        }
 
        dead = 0;
        len = cells.size();
        while (K > 0) {
            K--;
            for (i = 0; i < len; i++) {
                cells[i].t--;
                if (cells[i].t == -1) { // 비활성화 -> 활성화
                    activation.push(cells[i]);
                }
                if (cells[i].t == -cells[i].X) {    // 활성화 -> 죽음
                    dead++;
                }
            }
 
            while (!activation.empty()) {
                x = activation.top().x, y = activation.top().y, X = activation.top().X, activation.pop();
                for (i = 0; i < 4; i++)  {
                    nx = x + dir[i][0], ny = y + dir[i][1];
                    if (map[nx][ny] == 0) {
                        map[nx][ny] = X;
                        cells.push_back({ nx,ny,X, X });
                        len++;
                    }
                }
            }
        }
 
        cout << "#" << test_case << " " << len - dead << "\n";
    }
    return 0;
}

실행 결과

실행 결과 : Pass (816ms)