SW Expert Academy 5653 줄기세포배양 - C++

삼성의 대표 시뮬레이션 문제이다.

모의 SW 역량테스트에도 나온 만큼

최신 트렌드 시뮬레이션에 맞는 문제라고 할 수 있으며,

그만큼 문제를 제대로 읽고 제한 조건을 정확히 구현하는

연습에 아주 좋은 문제이다.

 

여기서 SW 역량테스트는 삼성 공채 SW 검정을 뜻한다.

 

구현하기 힘든 포인트는 다음과 같다.

 

1. 생명력 수치가 X인 세포는 X시간 동안 비활성화고 X시간이 되었을 때 활성된다.

2. 세포는 활성화된 후 X시간 살아있으며, 죽으면 그 자리를 그대로 차지한다.

3. 동시에 같은 셀에 번식하면 생명력 수치 X가 높은 줄기 세포가 혼자 차지한다.

4. 배양 용기 크기는 무한하다.

 

우선 1번, 생명력 수치X는 고정되어 있어야 하므로 (한 번 1이면 영원한 1!)

생명력 수치 X 와 세포의 나이 X` 을 구분해서 저장해 줘야 될 것 같다.

 

다음 2번, 죽은 세포는 다시는 활성화되지 않으며, 다른 세포가 번식할 일도 없다. 

고로 활성화된 후 한 번 번식하고 나면 다시는 해당 셀의 번식 관련 동작을 고려할 필요가 없다.

 

다음 3번, 같은 셀에 동시에 다른 세포가 번식할 경우, 가장 생명력 수치 X가 높은 세포만이

번식할 수 있으므로, 번식하려는 셀이 1) 이미 번식한 셀인지 2) 동일한 시기에 번식시도하는 셀인지

를 구분해서 구현해야 한다.

 

다음 4번, 물리적으로 제한된 메모리를 할당해줘야하기 때문에, 무한한 크기에 난감할 수 있는데,

최대 배양 시간 K 는 300 이하의 정수이고, 초기 줄기 세포 분포는 50x50 이 최대이므로

최종적으로 상하좌우로 350크기를 가질 수 있다.

고로 750 x 750 초과의 배열을 선언하고 중간 지점 (325, 325)를 중심으로 배치하면 된다.

#include <stdio.h>
#include <string.h>
#define MAX 350
int N, M, K;
int T;
  
typedef struct st {
    int y, x, X,time;//좌표, 생명력수치, 시간,
    int rem;//활성화까지 남은 시간
}QUEUE;
QUEUE queue[350 * 100 * 31];
int wp, rp;
  
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
void push(QUEUE x) { queue[wp++] = x; }
void pop() { ++rp; }
int empty() { return rp == wp; }
QUEUE front() { return queue[rp]; }
//가장 자리 없는 조건
//300시간(생명력1일떄) 50x50 크기로 주어지면 최대 150 성장하므로 총 크기는 350으로 한다.
int Map[350+1][350+1];
int visited[350+1][350+1];
  
  
  
int bfs() {
  
    register QUEUE cur;
    while (!empty()) {
        cur = front();
        if (cur.time >= K) return 0;
        pop();
        if (cur.X != Map[cur.y][cur.x]) continue;
          
        //printf("y : %d x : %d X %d timd %d rem %d\n", cur.y, cur.x,cur.X,cur.time,cur.rem);
        if (cur.rem!=0) {
            if (cur.rem - 1 > -cur.X) {
                QUEUE tmp = { cur.y,cur.x,cur.X,cur.time + 1, cur.rem - 1 };
                push(tmp);
            }
            continue;
        }
        for (register int i = 0; i < 4; ++i) {
            register int ny = cur.y + dy[i];
            register int nx = cur.x + dx[i];
            if (Map[ny][nx] >= cur.X ) continue;
            if (visited[ny][nx] < cur.time + 1) continue;
            Map[ny][nx] = cur.X;
            visited[ny][nx] = cur.time + 1;
            QUEUE tmp = { ny,nx, cur.X,cur.time+1, cur.X};
            push(tmp);
        }
        --cur.rem;
        ++cur.time;
        if (cur.rem > -cur.X) push(cur);
        /*
        for (int i = 350 - 10; i < 350 + N +12 ; i++) {
            for (int j = 350 - 10; j < 350 + M + 12; j++) {
                printf("%d", Map[i][j]);
            }
            printf("\n");
        }
        printf("\n");
        */
    }
    return 0;
}
int check() {
    QUEUE cur;
    register int ret = 0;
    while (!empty()) {
        cur = front(); pop();
        if (cur.X != Map[cur.y][cur.x]) continue;
        ret++;
    }
    return ret;
}
  
int solve() {
    bfs();
    register int ret = check();
    return ret;
}
  
int main() {
    scanf("%d", &T);
    for (register int loop = 0; loop < T; ++loop) {
        wp = rp = 0;
        memset(Map, 0, sizeof(Map));
        for (register int i = 0; i < MAX; ++i) {
            for (register int j = 0; j < MAX; ++j) {
                visited[i][j] = 500;
            }
        }
        scanf("%d %d %d", &N, &M, &K);
        for (register int i = 0; i < N; ++i) {
            for (register int j = 0; j < M; ++j) {
                scanf("%d", &Map[i + 150][j + 150]);
                if (Map[i + 150][j + 150]) {
                    QUEUE tmp = { i + 150, j + 150, Map[i + 150][j + 150] ,0,Map[i+150][j+150]};
                    push(tmp);
                    visited[i + 150][j + 150] = 0;
                }
            }
        }
        int ans = solve();
        printf("#%d %d\n", loop + 1, ans);
    }
    return 0;
}