7793

static char board[50][50];
static char visit[50][50];
static int N, M;
static int ny[4] = { 1, -1, 0, 0 };
static int nx[4] = { 0, 0, 1, -1 };
static queue<pair<int, int>> q[2]; //0: player, 1: devil

static int __solution(void)
{
	int depth = 1;
	while (!q[0].empty())
	{
		int q_size = q[1].size(); //악마를 먼저 확산
		for (int i = 0; i < q_size; i++)
		{
			pair<int, int> cur = q[1].front();
			q[1].pop();

			for (int cnt = 0; cnt < 4; cnt++)
			{
				int next_y = cur.first + ny[cnt];
				int next_x = cur.second + nx[cnt];

				if (next_y < 0 || next_y >= N || next_x < 0 || next_x >= M) //out of bound
					continue;

				char c = board[next_y][next_x];
				if (c != 'X' && c != 'D')
				{
					board[next_y][next_x] = '*';
					if (!visit[next_y][next_x])
					{
						visit[next_y][next_x] = '*';
						q[1].push({ next_y, next_x });
					}
				}
			}
		}

		q_size = q[0].size();
		for (int i = 0; i < q_size; i++)
		{
			pair<int, int> cur = q[0].front();
			q[0].pop();

			for (int cnt = 0; cnt < 4; cnt++)
			{
				int next_y = cur.first + ny[cnt];
				int next_x = cur.second + nx[cnt];

				if (next_y < 0 || next_y >= N || next_x < 0 || next_x >= M) //out of bound
					continue;

				char c = board[next_y][next_x];
				if (c == '.') //갈 수 있으면 
				{
					if (!visit[next_y][next_x])
					{
						visit[next_y][next_x] = 'S';
						q[0].push({ next_y, next_x });
					}
				}
				else if (c == 'D')
					return depth;
			}
		}
		depth += 1;
	}

	return -1;
}

static void solution(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++)
		scanf("%s\n", board[i]);

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			if (board[y][x] == 'S') //한번만  실행 됨
				q[0].push({ y, x });
			else if (board[y][x] == '*') //여러번 실행 됨
				q[1].push({ y, x });
		}
	}

	int ret = __solution();
	for (int i = 0; i < 2; i++)
		while (!q[i].empty())
			q[i].pop();
	memset(visit, 0, sizeof(visit));

	if (ret == -1)
		printf("GAME OVER\n");
	else
		printf("%d\n", ret);
}

문제의 키 포인트는 수정이가 갈 수 있는 위치와 악마를 확산 시키는 방법이다.

그리고 여기서 수정이의 위치를 먼저 이동 시킬지, 아니면 악마를 먼저 확산 시킬 지

그 순서를 정하는 방법은 크게 중요치 않다. 

다만, 악마를 먼저 확산시켜 수정이가 이동 할 수 있는 위치를 먼저 줄여 놓으면, 큐에 불필요하게 수정이가 이동할 좌표를 푸쉬 하지 않을 수 있다.