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

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

---

1. 이해하기

• 각 줄기 세포는 생명력이라는 수치를 가지고 있다.
  • 초기 상태에서 줄기 세포들은 비활성 상태이며 생명력 수치가 X인 줄기 세포의 경우 X시간 동안 비활성 상태이고 X시간이 지나는 순간 활성 상태가 된다.
  • 줄기 세포가 활성 상태가 되면 X시간 동안 살아있을 수 있으며 X시간이 지나면 세포는 죽게 된다.
  • 세포가 죽더라도 소멸되는 것은 아니다.
• 활성화된 줄기 세포는 첫 1시간 동안 상, 하, 좌, 우 네 방향으로 동시에 번식 한다.
• 번식된 줄기 세포는 비활성 상태이다.
• 두 개 이상의 줄기 세포가 하나의 그리드 셀에 동시 번식하려고 하는 경우 생명력 수치가 높은 줄기 세포가 해당 셀을 차지한다.
• K시간 후 살아있는 줄기 세포(비활성+활성)의 총 개수를 구하는 문제.
• 시뮬레이션 문제.

---

2. 구현하기

• 이 문제는 배열의 크기가 주어져 있지 않지만 생각하면 최대 범위를 구할 수 있다.

  • K+N+K, K+M+K이다.
  • 이유는 하나의 세포가 양 옆으로 퍼져나가기 때문이다.

• 세포가 퍼져나가는 것을 구현한다.

  • 세포가 퍼져나갈 수 없는 구역에 대해 알아보면, 셀에 세포가 죽어있거나 활성상태의 경우, 비활성상태이고 신규 세포가 아닌 경우이다.
  • 세포가 비활성상태이고 신규 세포이면 다른 세포가 퍼져나갈 때, 크기를 비교해서 크기가 큰 세포가 해당 셀을 차지할 수 있다.

  bool can_not_spread(int x, int y) {
      if(map[x][y].status == DEAD or map[x][y].status == ACTIVATE) return true;
      if(map[x][y].status == INACTIVATE and map[x][y].time != 0) return true;
      return false;
  }
  
  void spread(queue<Point>& q) {
      while(!q.empty()) {
          int x = q.front().x, y = q.front().y; q.pop();
          for(int i = 0; i < 4; i++) {
              int nx = x+dx[i], ny = y+dy[i];
              if(can_not_spread(nx,ny)) continue;
              if(map[nx][ny].status == INACTIVATE and map[nx][ny].time == 0) {
                  if(map[nx][ny].life_time < map[x][y].life_time) {
                      map[nx][ny].life_time = map[x][y].life_time;
                  }
              } else {
                  map[nx][ny] = {map[x][y].life_time,INACTIVATE,0};
              }
          }
      }
  }

• 퍼져나갈 세포를 찾는다.

  • 퍼져나갈 세포는 활성화 상태이고 지난 시간이 생명력 수치와 같을 때이다.

  queue<Point> will_spread_cell() {
      queue<Point> ret;
      for(int i = 0; i < N+K; i++) {
          for(int j = 0; j < M+K; j++) {
              if(map[i][j].status == ACTIVATE and map[i][j].time == map[i][j].life_time) {
                  ret.push({i,j});
              }
          }
      }
      return ret;
  }

• 시간이 경과하는 것을 구현한다.

  • 지난 시간이 자신의 생명력 수치와 같아질 때, 활성화 상태로 바꿔준다.
  • 생명력 수치의 두 배가 되면, 그 세포는 죽은 상태로 바꾼다.

  void time_pass() {
      for(int i = 0; i < N+K; i++) {
          for(int j = 0; j < M+K; j++) {
              if(map[i][j].status == NONE or map[i][j].status == DEAD) continue;
              map[i][j].time++;
              if(map[i][j].life_time == map[i][j].time) map[i][j].status = ACTIVATE;
              if(map[i][j].life_time*2 == map[i][j].time) map[i][j].status = DEAD;
          }
      }
  }

• K시간까지 시뮬레이션을 한다.

  void simulate() {
      for(int i = 0; i < K; i++) {
          queue<Point> spread_cell = will_spread_cell();
          time_pass();
          spread(spread_cell);
      }
  }

• K시간이 지난 후, 비활성+활성 상태의 세포의 수를 구한다.

  int count_cell() {
      int ret = 0;
      for(int i = 0; i < N+K; i++) {
          for(int j = 0; j < M+K; j++) {
              if(map[i][j].status == DEAD or map[i][j].status == NONE) continue;
              ret++;
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define NONE 0
#define DEAD 1
#define INACTIVATE 2
#define ACTIVATE 3
struct Point{
    int x,y;
};
struct Cell{
    int life_time,status,time;
};
Cell map[350][350];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N,M,K;

bool can_not_spread(int x, int y) {
    if(map[x][y].status == DEAD or map[x][y].status == ACTIVATE) return true;
    if(map[x][y].status == INACTIVATE and map[x][y].time != 0) return true;
    return false;
}

void spread(queue<Point>& q) {
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if(can_not_spread(nx,ny)) continue;
            if(map[nx][ny].status == INACTIVATE and map[nx][ny].time == 0) {
                if(map[nx][ny].life_time < map[x][y].life_time) {
                    map[nx][ny].life_time = map[x][y].life_time;
                }
            } else {
                map[nx][ny] = {map[x][y].life_time,INACTIVATE,0};
            }
        }
    }
}

queue<Point> will_spread_cell() {
    queue<Point> ret;
    for(int i = 0; i < N+K; i++) {
        for(int j = 0; j < M+K; j++) {
            if(map[i][j].status == ACTIVATE and map[i][j].time == map[i][j].life_time) {
                ret.push({i,j});
            }
        }
    }
    return ret;
}

void time_pass() {
    for(int i = 0; i < N+K; i++) {
        for(int j = 0; j < M+K; j++) {
            if(map[i][j].status == NONE or map[i][j].status == DEAD) continue;
            map[i][j].time++;
            if(map[i][j].life_time == map[i][j].time) map[i][j].status = ACTIVATE;
            if(map[i][j].life_time*2 == map[i][j].time) map[i][j].status = DEAD;
        }
    }
}

void simulate() {
    for(int i = 0; i < K; i++) {
        queue<Point> spread_cell = will_spread_cell();
        time_pass();
        spread(spread_cell);
    }
}

int count_cell() {
    int ret = 0;
    for(int i = 0; i < N+K; i++) {
        for(int j = 0; j < M+K; j++) {
            if(map[i][j].status == DEAD or map[i][j].status == NONE) continue;
            ret++;
        }
    }
    return ret;
}

void input() {
    memset(map,0,sizeof(map));
    cin >> N >> M >> K;
    for(int i = K/2; i < K/2+N; i++) {
        for(int j = K/2; j < K/2+M; j++) {
            int cell;
            cin >> cell;
            if(cell == 0) continue;
            else {
                map[i][j].life_time = cell;
                map[i][j].status = INACTIVATE;
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        simulate();
        cout << '#' << t << ' ' << count_cell() << '\n';
    }
    return 0;
}