2382. 미생물 격리

static int N, M, K;
static int board[2][100][100]; //현재, 다음, 방향
static int direction[2][100][100];
static int d[5][2] = {
	0, 0, //X
	-1, 0, //상
	1, 0, //하
	0, -1, //좌
	0, 1 //우
};
static int changed[] = { 0, 2, 1, 4, 3 };

static bool out_of_bound(int y, int x)
{
	if (y < 1 || y >= N - 1)
		return true;
	if (x < 1 || x >= N - 1)
		return true;
	return false;
}

static int solution()
{
	int y, x, n, dir, turn = 0, ret = 0;
	bool visit[100][100];
	int max[100][100];
	queue<pair<int, int>> q;

	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < K; i++)
	{
		scanf("%d %d %d %d", &y, &x, &n, &dir);
		board[turn][y][x] = n; //미생물 수
		direction[turn][y][x] = dir; //방향
		q.push({ y, x }); //좌표
	}

	for (int t = 0; t < M; t++)
	{
		int sz = q.size(); 

		ret = 0;
		memset(visit, false, sizeof(visit));
		memset(max, 0, sizeof(max));
		//현재 큐에 있는 개수만
		for (int cnt = 0; cnt < sz; cnt++)
		{
			pair<int, int> cur = q.front();
			q.pop();

			int y = cur.first, x = cur.second;
			int dir = direction[turn][y][x];
			int ny = y + d[dir][0], nx = x + d[dir][1];

			if (out_of_bound(ny, nx)) //약품 처리된 위치
			{
				board[1 - turn][ny][nx] += board[turn][y][x] / 2; //절반 줄여서 누적
				direction[1 - turn][ny][nx] = changed[dir]; //방향을 바꿈
				ret += board[turn][y][x] / 2; //결과 누적
			}
			else
			{
				board[1 - turn][ny][nx] += board[turn][y][x]; //그대로 누적
				if (board[turn][y][x] > max[ny][nx]) //군집의 수가 더 많으면
				{
					max[ny][nx] = board[turn][y][x]; //최대 군집의 수 초기화
					direction[1 - turn][ny][nx] = dir; //그 군집의 방향으로 초기화
				}
				ret += board[turn][y][x]; //결과 누적
			}

			board[turn][y][x] = 0; //이동했으니 현재 위치는 초기화
			direction[turn][y][x] = 0;
			if (!visit[ny][nx]) //큐에 없는 좌표라면
			{
				q.push({ ny, nx });
				visit[ny][nx] = true;
			}
		}

		turn = 1 - turn; //다음으로 이동
	}

	memset(board, 0, sizeof(board));
	return ret;
}

처음에는 현재 위치의 군집의 이동 방향을 board에 같이 저장하는 방식으로 하였다. 그러나 이 경우 한가지 문제가 있었다. 

board[2][ny][nx] = dir 또는 changed[dir] 시 다음에 확인 할 좌표에 방향이 미리 바뀔 수 있다는 것이다.

그래서 board처럼 direction도 현재, 다음 저장 을 위한 배열을 추가로 생성하여 이 문제를 해결 하였다.

 

그리고 동시에 확산하기 때문에 하나의 셀이 여러 군집이 모일 수 있는데,

각 군집 당 체크하면서 선형 탐색으로 충분히 해결 할 수 있다.

 

또 동시에 라는 말이 나오면 turn = 1 - turn 을 적어 놓고 시작하는 것이 낫겠다.

 

마지막으로 언급 할 점은 turn = 1 - turn의 삽입 위치이다. 문제를 풀면서 실수를 하지 않은 부분이지만,

코드가 길어지면 해당 코드의 삽입 위치를 실수 할 수 있다.

다시 한번 생각해 볼 만한 점이다.

 

 

//주의사항 및 정리

1. 메모리를 많이 사용하는 것에 부담가지지 말 것, 힙영역 256MB는 int형 배열의 길이를 최대 6400만개 까지 할당 할 수 있다. 1000 * 1000 사이즈 배열을 64개 까지 만들 수 있으니 걱정하지 말 것.

2. 문제에서 방향을 1, 2, 3, 4 형식으로 준다. 별다른 언급이 없으면 나는 주로 0, 1, 2, 3으로 처리하기 때문에 놓치지 말아야할 부분이다. 그리고 이 경우 d[5][2]로 하고 d[0] = {0, 0} 으로 한다. 물론 dir = 1 부터 시작하긴 하지만 만약의 경우를 위해서 이다.