5653. 줄기세포배양

static int N, M, K; //height, width, time
static int board[800][800]; //timer
static int state[800][800]; //1 -> 2 -> 3 : end
static int org[800][800]; //original value
static int winner[800][800]; //maximum
static int d[4][2] = {
	-1, 0, //up
	1, 0, //down
	0, -1, //left
	0, 1 //right
};

static int solution()
{
	queue<pair<int, int>> q;
	queue<pair<int, int>> qq;

	scanf("%d %d %d", &N, &M, &K);
	for (int y = 400; y < 400 + N; y++)
	{
		for (int x = 400; x < 400 + M; x++)
		{
			scanf("%d", &board[y][x]);
			org[y][x] = board[y][x];
			if (board[y][x] > 0) //생명력이 존재
			{
				state[y][x] = 1; //비활성 상태로 설정
				q.push({ y, x }); //비활성 상태이므로 큐잉
			}
		}
	}

	for (int t = 0; t < K; t++)
	{
		int sz = q.size();
		//모든 활성, 비활성 좌표에 대해서
		for (int i = 0; i < sz; i++) //phase1,
		{
			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] += 1; //next state
					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]) //이미 점유된 셀이면 패스,
						continue;
					if (!winner[ny][nx]) //아직 확산되지 않은 곳이면
						qq.push({ ny, nx }); //생명력 결정을 위해 큐잉
					if (board[y][x] > winner[ny][nx]) //생명력이 더 높은 값에 대해서
						winner[ny][nx] = board[y][x];
				}

				if (board[y][x] > 0)
					board[y][x] -= 1; //타이머 동작
				if (board[y][x] == 0) //타이머 만료
					state[y][x] += 1; //next state
				else
					q.push({ y, x }); //아직 활성 상태이므로 큐잉
			}
		}

		//확산될 모든 위치에 대해서
		while (qq.size()) //phase2, 
		{
			pair<int, int> cur = qq.front();
			qq.pop();

			int y = cur.first, x = cur.second;
			state[y][x] = 1; //비활성 상태
			board[y][x] = winner[y][x]; //생명력이 제일 높은 것으로 타이머 설정
			//확산되는 위치의 경우 org값이 0이므로 타이머와 같은 값으로 다시 설정해야 함.
			org[y][x] = winner[y][x]; 
			q.push({ y, x }); //비활성 상태이므로 큐잉
			//어차피 상태 정보로 인해 더 이상 참조 될 수 없으므로 초기화
			winner[y][x] = 0; 
		}
	}

	memset(board, 0, sizeof(board));
	memset(org, 0, sizeof(org));
	memset(state, 0, sizeof(state));
	return q.size(); //q에는 비활성, 활성 상태의 좌표 정보만 존재
}

첫번째로 언급할 점은 무한한 공간이라는 것이다. 무한한 공간을 표현하기 위해 조건이 허락하는 범위내에서 가능한 크게 이차원 배열을 할당하였고, 입력의 시작은 해당 배열의 중간쯤이 되도록 하였다.

 

시뮬레이션 문제를 풀 때 초점을 맞춰야 할 부분이 있다면 그것은 바로 상태 천이이다.

위 문제에서는 타이머 개념이 존재하여 다시 풀 때 에는 이 타이머 쪽에 초점을 맞추어서 풀이를 시작했는데, 생각외로 문제가 많았다. 아직도 그 원인이 무엇인지 파악하지 못해서, 예전에 작성했던 코드를 다시 참조해보았다.

--> 방향 이동을 위한 배열로 주로 static int d[4][2] = {...}; 이렇게 사용하는데,

     문제가 있던 코드에서는 static int d[2][4] = {....}; 이렇게 되어 있었다. column과 row가 뒤바뀐 것이다.

     아예 처음 부터 다시 작성했을 때는 이러지 않았는데, 왜 처음에 코드를 작성할 때에는 이렇게 된 건지 알 수가 없다.

     외워야겠다. "스태틱 인트 4 2"

 

참조한 코드는 상태에 따라 그 처리를 하였다. FSM처럼 말이다.

그래서 가급적 상태에 따라 처리하도록 코드를 작성하도록 해야겠다. 그리고 이렇게 하는 편이 코드 작성 시 더 눈에 잘 띄는 거 같기도 하다.

 

//주의사항 및 정리

1. 예전에 타이머가 0보다 작아지는 문제가 있었다. 이 부분은 항상 조심해야 한다.

2. 번식의 경우 번식의 대상이 되는 위치의 경우 원래 값은 항상 0이다. 따라서 적절한 순간에 적절히 해당 부분을 초기화 시켜주어야 한다.

3. 반복문 안에 여러 step들이 들어가는 경우, 해당 step이 정확히 어느 시점에 동작해야하는지를 염두하여 코드를 작성해야 한다. 확산을 마무리 하는 단계가 두 번째 for문안에 들어가 있었다.

4. 특정 위치를 바로 접근해야 하는 경우를 위해 주로 큐에다 좌표 정보를 적어두고 활용하는 식으로 코드를 작성하는데,

list를 이용하여 iteration하면서 필요한 부분에서는 erase하고 그 반환 값을 다음 iterator로 활용하는 식으로 코드를 작성하는 것도 괜찮을 것 같다. 큐에 해당 좌표를 다시 삽입해야 하는 코드를 까먹을 수 도 있으니 말이다.

5. 동시에 여러 미생물들이 확산되는데 그 중 생명력이 가장 높은 것을 선택하기 위해서는 비교를 해나가면서 가장 큰 값을 선택하고 마지막에 일괄처리하도록 해야한다.