[백준 16920] 확장 게임

https://www.acmicpc.net/problem/16920

16920번: 확장 게임

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
int R, C, P;
char board[1000 + 2][1000 + 2];

struct _vt
{
	int x, y;
	int move;
};

struct _st
{
	bool spread;
	int speed;
	int castle;	// 성좌표를 굳이 벡터에 저장할 필요 없음 .. 
};
_st Player[9 + 2];

std::queue<_vt> Q[9 + 2];
std::queue<_vt> TMP;
int visited[1000 + 2][1000 + 2];

void input()
{
	scanf("%d %d %d", &R, &C, &P);
	for (int i = 1; i <= P; i++) {
		scanf("%d", &Player[i].speed);
	}

	for (int r = 0; r < R; r++) {
		scanf("%s", &board[r]);
		for (int c = 0; c < C; c++) {
			if (board[r][c] >= '1' && board[r][c] <= '9') {	// 숫자인것만 받아주어야 함 !!! 벽이 있을 수 잇다 
				int p_num = board[r][c] - '0';
				Q[p_num].push({ r, c , 0});
				visited[r][c] = p_num;
				Player[p_num].castle++;
			}
		}
	}
}

// 버퍼큐 놓고 큐 계속 갈아 끼우면 그 횟수가 1000번이 넘어갈 때는 시간초과 날 수 있다.. 
void BFS(int p_num)
{
	// dir
	int dir_x[4] = { 0, 0 ,1 ,-1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	// init
	TMP = {};
	bool now = false;

	if (Q[p_num].empty()) {
		Player[p_num].spread = false;
		return;
	}

	while (!Q[p_num].empty()) {
		_vt data = Q[p_num].front();
		Q[p_num].pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == '#')continue;
			if (visited[nx][ny]) continue;
			if (data.move + 1 == Player[p_num].speed) TMP.push({ nx, ny, 0 });
			else Q[p_num].push({ nx, ny, data.move + 1 });
			visited[nx][ny] = p_num;
			Player[p_num].castle++;
			now = true;
		}
	}
	Q[p_num] = TMP;
	Player[p_num].spread = now;
}




bool chk_done()
{
	for (int i = 1; i <= P; i++) {
		if (Player[i].spread == true) return false;
	}
	return true;	// 모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 
}


void simulation()
{
	while (1) {
		// move players
		for (int i = 1; i <= P; i++) {
			BFS(i);
		}
		//debug();
		// chk
		if (chk_done()) return;
	}
}

void output()
{
	for (int i = 1; i <= P; i++) {
		printf("%d ", Player[i].castle);
	}
	printf("\n");
}


int main()
{
	input();
	simulation();
	output();
	return 0;
}

1. 3번의 oob는 인풋 받을 때 벽이 있는 경우를 생각 못하고 board[r][c] != '.' 일때 구조체에 담으라고 했기 때문이다.. 

이런거 설계 좀 잘하자.. 어떤 것들이 입력 받아지는지 잘 생각하면서 코드 짜자.. 

 

2. 시간초과가 난 이유는 버퍼큐를 큐 돌릴 때 마다 갈아끼워주었기 때문이다. 최악의 경우 1000 * 1000 맵에서 Si가 1000일 때 그만큼 큐를 계속 갈아끼워준것.. 

해결한 방법은 상태를 발전시킬 맨 마지막 원소들(해당 문제에서는 data.move + 1 == Player[p_num].speed) 만 버퍼큐에 넣어놓고 큐가 비어서 루프를 빠져나오면 가장 마지막에 한 번 갈아끼워주는 것이다. 

이때도 주의해야할 점.. data.move 가 아니라 data.move + 1 이랑 비교해주어야 한다.. 왜냐하면 (nx, ny)이니까 현재에서 한 칸 이동한 다음 좌표이므로 move 수도 한 칸 늘어남....