[Swea] 줄기세포배양 (c++) 구현, 범위 나누기

출처 : https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

풀이 방법

Cell 구조체를 정의하고 operator <를 정의해서 시간이 적은 순으로 만약 시간이 같다면 생명력이 높은 순으로 우선순위 큐에 저장해서, 세포들을 저장하며, bfs를 수행하면 된다.

Cell의 구조체는 y, x, time, life를 저장하는데 time은 활성화한 후 1시간 후인 즉 번식하는 시간으로 설정했다.

 

그리고 K시간 후 남아 있는 줄기 세포를 계산하기 위해 time -1 -life <= K < time + life -1 이면 비활성, 활성 상태 속한다는 의미이므로 정답을 구하는 변수인 ans를 +1 해주었다. 이 부분이 가장 헷갈렸고, 다음부턴 예시를 통해 정확하게 구별하도록 하자 =<라는 문법 실수도 있었다.

 

또한 줄기세포가 좌표 범위를 넘어가 번식을 못하는 경우가 없으므로 줄기세포를 저장하는 lab의 범위설정도 중요했다. 다른 사람의 풀이를 보니 351로 설정해도 통과가 가능하다고 한다. 하지만 난 그냥 넉넉하게 700으로 잡았다. 배열을 중간쯤 부터 초기 줄기세포를 할당했다. 즉 330부터 할당했다. 

 

#include<iostream>
#include<memory.h>
#include<queue>

using namespace std;


// x시간 동안 비활성 X시간 동안 살아 있을 수 있다.
// 죽은 상태가 되므로 셀을 차지한다.
// 첫 1시간 동안 상하좌우
// 번식된 줄기 세포는 비활성화 상태이다.
// 동시 접근 시 생명력이 높은 줄기 세포가 가능
// 
int lab[700][700]; // 0은 세포 나이 1은 세포 가능 시간
int T, N, M, K, ans;
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};

struct Cell {
    int y;
    int x;
    int life;
    int time;

    Cell(int y, int x, int life, int time) : y(y), x(x), life(life), time(time) {        
    }

    bool operator < (const Cell c) const{
        if (time > c.time) return true; // time이 작은 거 부터 오게
        else if (time == c.time) {
            if (life < c.life) return true; // life가 큰 거 부터 나오게
            else return false;
        }
        else return false;
    }
};

priority_queue<Cell> c;

void Input() {
    cin >> N >> M >> K;
    memset(lab, 0, sizeof(lab));    
    for (int i = 330;i < 330 + N;i++) {
        for (int j = 330;j < 330 + M;j++) {
            int a;
            cin >> a;
            lab[i][j] = a;  
            if (a > 0) {
                c.push(Cell(i, j, a, a+1));
            }          
        }
    }
}

void bfs() {    
    while (!c.empty()) {
        Cell now = c.top();
        c.pop();
        int y = now.y;
        int x = now.x;
        int life = now.life;
        int time = now.time;
        if (time - 1 - life <= K && K < time + life - 1) { 
            ans++; // 활성 or 비활성 상태
        }        
                
        if (time <= K) {
            for (int i = 0;i < 4;i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (lab[ny][nx] > 0) continue; // 이미 있으면 pass
                lab[ny][nx] = life;
                c.push(Cell(ny, nx, life, time + life + 1)); // 다음 번식하는 상태로 이동
            }
        }
        
    }
    return ;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    for (int i = 0;i < T;i++) {
        ans = 0;
        Input();
        bfs();        
        cout << "#" << i+1 << " " << ans << '\n';
    }

    return 0;
}