static int N, M, K;
static int board[1024][1024];
static int state[1024][1024];
static int org[1024][1024];
static int tmp[1024][1024];
static int d[4][2] = {
-1, 0, //up
1, 0, //down
0, -1, //left
0, 1 //right
};
static int solution(void)
{
queue<pair<int, int>> q;
queue<pair<int, int>> qq;
scanf("%d %d %d", &N, &M, &K);
for (int y = 512 - N, cnt1 = 0; cnt1 < N; y++, cnt1++)
{
for (int x = 512 - N, cnt2 = 0; cnt2 < M; x++, cnt2++)
{
scanf("%d", &board[y][x]);
org[y][x] = board[y][x];
if (org[y][x] > 0)
{
state[y][x] = 1; //비활성,
q.push({ y, x });
}
}
}
//memcpy(org, board, sizeof(board));
for (int t = 0; t < K; t++)
{
int q_sz = q.size();
for (int cnt = 0; cnt < q_sz; cnt++)
{
pair<int, int> cur = q.front();
q.pop();
int y = cur.first, x = cur.second;
if (state[y][x] == 1) //비활성,
{
if (board[y][x] > 0)
board[y][x] -= 1;
if (board[y][x] == 0)
{
state[y][x] = 2; //활성상태로 변경
board[y][x] = org[y][x];
}
q.push({ y, x });
}
else if (state[y][x] == 2) //활성,
{
for (int dir = 0; dir < 4; dir++)
{
int ny = y + d[dir][0];
int nx = x + d[dir][1];
if (!state[ny][nx]) //번식가능한 영역,
{
if (!tmp[ny][nx])
qq.push({ ny, nx });
if (board[y][x] > tmp[ny][nx])
tmp[ny][nx] = board[y][x];
}
}
if (board[y][x] > 0)
board[y][x] -= 1;
if (board[y][x] > 0)
q.push({ y, x });
else
state[y][x] = 3; //죽은상태로 변경,
}
}
while (qq.size())
{
pair<int, int> cur = qq.front();
qq.pop();
int y = cur.first, x = cur.second;
q.push({ y, x });
state[y][x] = 1; //비활성상태로,
board[y][x] = tmp[y][x];
org[y][x] = tmp[y][x]; /***놓쳤던 부분***/
tmp[y][x] = 0; //초기화,
}
}
memset(state, 0, sizeof(state));
return q.size();
}시뮬레이션 하는 문제이다.
비슷한 유형의 문제를 여러번 풀어보았고, 특히, 동시에 같은 영역을 차지하려는 부분 역시 2382번 문제에서 적용했던 방식을 그대로 적용하면 될 거라는 확신과 함께 문제를 풀어 보았다.
먼저, 배양 용기의 크기는 무한하다고 가정한다는 조건이 있다. 그래서 배열을 좀 큰 범위 잡았다.
가로 * 세로 = (300 * 2 + 50) * (300 * 2 + 50) 정도로 잡으면 될 것 같다.
그러나 일부러 좀 더 큰 값을 잡아 처리하였다. 어차피 1024 * 1024 = 1M 정도 이므로 주어진 메모리 공간을 초과하지는 않기 때문이다.
입력의 시작은 이러한 큰 배열의 중간 쯤에 위치한 곳에서 부터 저장하였다.
확산을 위함이다.
그리고 줄기세포의 상태는 크게 3가지가 있다. 비활성, 활성, 죽음 인데 초기 입력에서 1이상인 값들이 위치한 곳을 비활성 상태로 둔다.
시간의 흐름은 반복문을 통해 처리한다.
그리고 현재 큐에 있는 좌표의 개수 만큼 pop하여 처리를 하는데,
board 배열에 각 원소는 타이머 역할을 한다. 그리고 org는 원래 값을 저장하는데, 주의해서 다루어야 한다. 그 내용은 뒤에서 다시 다루겠다.
활성상태에서는 먼저 확산을 시도한다. state가 0인 곳은 확산할 수 있는 영역이다.
그리고 tmp가 0인 곳은 아무도 확산을 시도하지 않은 영역이므로 qq에 푸쉬한다.
그 다음 동시에 같은 곳으로 번식하려는 것 들 중에 생명력이 높은 것을 찾기 위해 비교연산을 하여,
최대 값을 찾아낸다.
마지막은 가장 중요한 반복문이라고 볼 수 있다.
확산된 줄기세포들의 상태 및 값을 정하는 단계이다.
다른 것들은 쉽게 이해가 가능하다. 그러나 한가지 놓쳤던 부분이 있었다.
org 값을 설정하지 않았던 것이다.
초기 입력에서 0인 위치는 확산이 가능한 부분이다.
그래서 org값도 0이다.
그러나 이 부분을 생각하지 못해서 답이 계속 틀리는 문제가 있었다.
비활성 부분을 처리하는 곳에서 board값을 org에 있는 것으로 재초기화 하는 부분이 있는데,
여기서 문제가 있던 것 이었다.
다른 것 보다 이 부분에 대해서 인지하지 못하고 있었던 것이 풀이에 큰 영향을 주었던 것 같다.
