[SWEA 5653] 줄기세포배양

문제 : 5653. [모의 SW 역량테스트] 줄기세포배양

[문제 출처] : SW Expert Academy [모의 SW 역량테스트] - 줄기세포배양

 

 

이번 문제를 구현하는 데에는 생각 없이 그냥 단순하게 구현할 수 있었다 다만 변수의 명명을 명확하게 

하지 않아 실수해 시간을 조금 많이 썼다 대충 변수 이름을 지어버려 의도치 않게 다른 큐를 사용해 디버깅

하느라 아까운 시간을 날렸다.. 

 

이번 문제 같은 경우는 차량 정비소 문제와 미생물 격리를 풀기 위해서 썼던 자료구조와 시간의 흐름을 코드로

구현하는 방법이 매우 비슷하다고 느꼈다

 

[문제 풀이]

 

이번 문제를 풀 때 격자 (board)에 대한 언급이 없고 "시뮬레이션에서 배양 용기의 크기는 무한하다고 가정한다."

라는 조건 때문에 격자를 쓰지 않고 풀어야 하나?라고 생각을 했다 근데 주어진 문제의 조건을 조금 살펴보면

 

격자를 이용해도 문제없음을 알 수 있다!  배양 시간 k 는 (1≤K≤300)이고 n과 m 역시 (1≤N≤50, 1≤M≤50) 이기 때문에 

50 x  50 격자에서 시작해 빠르게(생명력 : 1)  최대 시간 K = 300으로 배양을 시작한다고 해도 

격자는 양쪽으로 300씩 650 언저리까지 뻗어 나갈 것으로 생각해 볼 수 있다 그래서 격자를 1000으로 잡고

입력으로 주어지는 격자를 가운데서부터 입력을 받았다

 

비활성 상태 및 활성 상태의 줄기세포는 단순하게 자료구조 큐를 활용하였다 또한 주어진 문제의 조건 

"두 개 이상의 줄기 세포가 하나의 그리드 셀에 동시 번식하려고 하는 경우 생명력 수치가 높은 줄기 세포가

해당 그리드 셀을 혼자서 차지하게 된다."  를 처리하기 위해서 

활성 상태의 줄기세포를 관리하는 큐에서는 우선순위 큐를 활용하였다

 

 

struct Node {
    int x, y;        // 위치
    int time;        // time 시간이 지나 활성상태가 되고  time 시간 동안 살아 있을 수 있다.
    int figure;     // 생명력
    Node(int x, int y, int t, int f) : x(x), y(y), time(t), figure(f) {}
    bool operator <(const Node tmp) const {
        return this->figure < tmp.figure;
    }
};

여기서 노드 내부에 연산자를 재정의 한 것은 생명력 수치가 높은 줄기 세포부터 처리하기 위함이다.

이해가 되지 않는다면 밑에 글을 참고해보면 좋을 것 같다

'C++ STL' 카테고리의 글 목록

 

queue<Node> q;               // 비활성 상태 줄기세포를 관리
priority_queue<Node> nq;    // 활성 상태 줄기세포를 관리

 

또한 큐를 사용해야 할 때의 주의점으로 활성 줄기세포를 관리하기 위해서 큐에서 원소를

꺼내어 시간 관련 작업을 해주어야 한다 (생명력이 X인 줄기세포는 X시간 동안 살아 있을 수 있다)  작업 후 다시 똑같은 큐에다가 원소를 넣어 주게 되면 똑같은 원소가 다시 한번 꺼내어지게 되는 실수를 범할 수도 있다

임의의 큐를 생성해 꺼낸 다음은 임의의 큐에 넣고 마지막으로 다시 원래의 큐에 넣어주는 작업을 해주면 된다

 

 

[소스 코드]

 

#include <iostream>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
int n, m, k;
const int MAX = 1000;
int f = MAX / 2;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
int map[MAX][MAX];
struct Node {
    int x, y;        // 위치
    int time;        // time 시간이 지나 활성상태가 되고  time 시간 동안 살아 있을 수 있다.
    int figure;        // 생명력
    Node(int x, int y, int t, int f) : x(x), y(y), time(t), figure(f) {}
    bool operator <(const Node tmp) const {
        return this->figure < tmp.figure;
    }
};
void db() {
    for (int i = 0; i < 30; i++) {
        for (int j = 0; j < 30; j++) {
            cout << map[i][j] << ' ';
        }
        cout << "\n";
    }
    cout << "\n";
}
int main(int argc, char** argv) {
    int test_case, T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> n >> m >> k;
        queue<Node> q;
        priority_queue<Node> nq;
        memset(map, 0, sizeof(map));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> map[i + f][j + f];
                if (map[i + f][j + f] == 0) continue;
                else q.push(Node(i + f, j + f, map[i + f][j + f], map[i + f][j + f]));
            }
        }
        /*
          cout << "초기 상태 : " << '\n';                             
         db();
       */
        queue<Node> tq;
        priority_queue<Node> tnq;
        for (int cnt = 1; cnt <= k; ++cnt) {
            //  활성화 상태 ----> 비활성 상태
            while (!nq.empty()) {
                Node nt = nq.top(); nq.pop();
                int tt = nt.time;
                for (int dir = 0; dir < 4; ++dir) {
                    int nx = nt.x + dx[dir];
                    int ny = nt.y + dy[dir];
                    if (map[nx][ny] != 0) continue;
                    map[nx][ny] = nt.figure;
                    tq.push(Node(nx, ny, nt.figure, nt.figure));
                }
                if ((tt + 1) != nt.figure)
                    tnq.push(Node(nt.x, nt.y, tt + 1, nt.figure));
            }
            //  비활성화 상태  ---->   활성상태
            while (!q.empty()) {
                Node t = q.front();
                int tt = t.time;
                q.pop();
                tt--;
                if (tt == 0) {
                    nq.push(Node(t.x, t.y, tt, t.figure));
                    continue;
                }
                else tq.push(Node(t.x, t.y, tt, t.figure));
            }
            while (!tq.empty()) q.push(tq.front()), tq.pop();
            while (!tnq.empty()) nq.push(Node(tnq.top())), tnq.pop();
        /*    cout << "Time After : " << cnt << '\n';
            db();
            cout << "활성화 상태에 있는 세포 : " << nq.size() << "\n";
            cout << "비활성화 상태에 있는 세포 : " << q.size() << "\n";
        */
        }
        int ans = 0;
        while (!q.empty()) ans += 1, q.pop();
        while (!nq.empty()) ans += 1, nq.pop();
        cout << "#" << test_case << ' ' << ans << '\n';
    }
    return 0;
}