요약
qNow와 qNext를 이용해서 한 단계가 전부 끝나고 난 이후에 다음 단계가 진행될 수 있도록 했다.
문제
줄기세포들을 배양 용기에 도포한 후 일정 시간 동안 배양을 시킨 후 줄기 세포의 개수가 몇 개가 되는지 계산하는 시뮬레이션 프로그램을 만들어야 한다.
각 줄기 세포는 생명력이라는 수치를 가지고 있다.
초기 상태에서 줄기 세포들은 비활성 상태이며 생명력 수치가 X인 줄기 세포의 경우 X시간 동안 비활성 상태이고 X시간이 지나는 순간 활성 상태가 된다.
줄기 세포가 활성 상태가 되면 X시간 동안 살아있을 수 있으며 X시간이 지나면 세포는 죽게 된다.
세포가 죽더라도 소멸되는 것은 아니고 죽은 상태로 해당 그리드 셀을 차지하게 된다.
활성화된 줄기 세포는 첫 1시간 동안 상, 하, 좌, 우 네 방향으로 동시에 번식을 한다.
번식된 줄기 세포는 비활성 상태이다.
하나의 그리드 셀에는 하나의 줄기 세포만 존재할 수 있기 때문에 번식하는 방향에 이미 줄기 세포가 존재하는 경우 해당 방향으로 추가적으로 번식하지 않는다.
두 개 이상의 줄기 세포가 하나의 그리드 셀에 동시 번식하려고 하는 경우 생명력 수치가 높은 줄기 세포가 해당 그리드 셀을 혼자서 차지하게 된다.
줄기 세포의 크기에 비해 배양 용기의 크기가 매우 크기 때문에 시뮬레이션에서 배양 용기의 크기는 무한하다고 가정한다.
[제약 사항]
초기 상태에서 줄기 세포가 분포된 영역의 넓이는 세로 크기 N, 가로 크기 M이며 N, M은 각각 1 이상 50 이하의 정수이다. (1≤N≤50, 1≤M≤50)
배양 시간은 K시간으로 주어지며 K는 1 이상 300 이하의 정수이다. (1≤K≤300)
배양 용기의 크기는 무한하다. 따라서 줄기 세포가 배양 용기 가장자리에 닿아서 번식할 수 없는 경우는 없다.
줄기 세포의 생명력 X는 1 이상 10 이하의 정수이다. (1≤X≤10)
[입력]
각 테스트 케이스의 첫째 줄에는 초기 상태에서
줄기 세포가 분포된 세로 크기 N, 가로 크기 M, 배양 시간 K가 순서대로 주어진다.
다음 N 줄에는 각 줄마다 M개의 그리드 상태 정보가 주어진다.
1~10까지의 숫자는 해당 그리드 셀에 위치한 줄기 세포의 생명력을 의미하며,
0인 경우 줄기 세포가 존재하지 않는 그리드이다.
[출력]
배양을 K시간 시킨 후 배양 용기에 있는 살아있는 줄기 세포(비활성 상태 + 활성 상태)의 개수를 출력한다. 풀이
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <queue>
using namespace std;
struct Edge {
int row, col, state, chlife, life;
};
struct cmp {
bool operator()(Edge a, Edge b) {
if (a.life < b.life) return true;
return false;
}
};
int arr[700][700] = { 0, };
int used[700][700] = { 0, };
queue <Edge> qNow;
queue <Edge> qNext;
priority_queue<Edge, vector<Edge>, cmp> qStart;
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
int N, M, K;
cin >> N >> M >> K;
int cell = 0;
for (int i = 320; i < N + 320; i++) {
for (int j = 320; j < M + 320; j++) {
cin >> arr[i][j];
int a = arr[i][j];
if (a)
{
qStart.push({ i,j,-1,a,a });
cell++;
used[i][j] = 1;
}
}
}
while (!qStart.empty())
{
qNow.push(qStart.top());
qStart.pop();
}
for (int i = 1; i <= K; i++) {
while (!qNow.empty())
{
Edge now = qNow.front();
qNow.pop();
int state = now.state;
int life = now.life;
int chlife = now.chlife;
int pr = now.row;
int pc = now.col;
used[pr][pc] = 1;
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
if (state == -1)
{
chlife--;
if (chlife == 0) qNext.push({ pr,pc,1,life,life });
else qNext.push({ pr,pc,state,chlife,life });
}
if (state == 1)
{
chlife--;
if (chlife == 0) cell--;
else qNext.push({ pr,pc,state,chlife,life });
for (int d = 0; d < 4; d++) {
int nr = pr + dr[d];
int nc = pc + dc[d];
if (used[nr][nc]) continue;
used[nr][nc] = 1;
qNext.push({ nr,nc,-1,life,life });
cell++;
}
}
}
while (!qNext.empty())
{
qNow.push(qNext.front());
qNext.pop();
}
}
cout << "#" << tc << " " << cell << endl;
for (int i = 0; i < 700; i++) {
for (int j = 0; j < 700; j++) {
arr[i][j] = 0;
used[i][j] = 0;
}
}
while (!qNow.empty())
{
qNow.pop();
}
}
return 0;
}