[코드트리] 팩맨 (C++)

[문제]

https://www.codetree.ai/training-field/frequent-problems/problems/pacman/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

[설명]

시간초과가 조금 무서웠던 문제... 벡터로 몬스터 구조체를 관리했는데, 죽은 몬스터들도 모두 넣었기에 순차탐색 * board크기시 시간초과 날 가능성이 있어보였다.

 

턴이 진행되는 동안 살아있는 몬스터의 수가 100만개가 넘는 입력은 주어지지 않는다고 가정해도 좋습니다.

 

지금 생각해도 위조건을 생각해도 죽은 몬스터까지 하면 1000만개가 되면 위험해지는데 괜찮은건지 모르겠다.

 

 

 총 4가지의 방향을 3칸 이동하기 때문에 총 64개의 이동 방법이 존재하는데, 이 중 몬스터를 가장 많이 먹을 수 있는 방향으로 움직이게 됩니다.

 

제일 어려운 풀이는 팩맨 이동 과정이었는데, 사실 위 지문을 힌트로 쉽게 생각할 수 있었다. 4가지 방향을 3번 for문을 돌려서 모든 이동을 해보고, 가장 높은 점수를 구하고, 그때 방향을 저장해주면 되는 거였다.

 

처음 간과한 사실은 팩맨이 먹으면서 모든 경우 탐색시 이동하는데 이전 몬스터들을 그냥 놓았다가 틀렸다.  다른 board를 만들어서,  각 for문 마다 board에 대입해 임시 보드를 사용할지 고민했는데, 그냥 지나간 자리와 거기의 몬스터 수를 임시저장했다가 이번 3중 for문이 끝나면 돌려주는 방식을 사용했다. 

두 방법 다 코드가 더러워질 것 같기에 별로 하고싶지는 않았다... 

 

애매한 상황이라고 생각한건 시체가 있는자리에서 다른 몬스터가 죽었을때 시체가 사라지는 시간이었다. 근데 시체가 여러개든 한개든 어차피 사라지는 시간은 최대 시간으로 기록되기에 그냥 겹쳐져서 죽더라도 사라지는 시간은 하나로 통일되게 하였다.

 

 

 

[코드]

#include <iostream>
#include <vector>

using namespace std;
#define X first
#define Y second

int M, T;
int pac_x, pac_y;
int score;
int global_time;

struct monster {
	int num;
	int x, y;
	int dir;
	bool born; //태어날 턴 수
	bool in;
	bool die;
};
vector <monster> monsters;
int board[4][4];

int dead[4][4]; //시체 존재 위치 보임. 시체가 중복된 시간에 두개 가능?
int finish[4][4]; //시체 없어질 턴 수

int dx[8] = { -1,-1,0,1,1,1,0,-1 }; //상부터 반시계
int dy[8] = { 0,-1,-1,-1,0,1,1,1 };
int dx1[4] = {-1,0,1,0}; //상부터 반시계
int dy1[8] = {0,-1,0,1 };
int eat[64]; //방향별 먹을 수 있는 수

void duplicate(monster me) {
	M++;//총 몬스터 수 

	monsters.push_back({M,me.x,me.y,me.dir,true,false,false });
}
void move(monster me) {
	int origin_dir = me.dir;
	int first_flag = false;
	while (true)
	{
		int nx = me.x + dx[me.dir];
		int ny = me.y + dy[me.dir];
		if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4 || dead[nx][ny] > 0 || (nx == pac_x && ny == pac_y)) {
			if (first_flag && origin_dir == me.dir) break; //바꿨는데도 조건문 안으로
			me.dir = (me.dir + 1) % 8;
			if (!first_flag) first_flag = true;
			continue; //밑에거 안하고, 다시 시도
		}
		//조건에 안걸리면 이동
		board[me.x][me.y]--;
		board[nx][ny]++;
		me.x = nx;
		me.y = ny;
		monsters[me.num] = me;
		break;
	}
}
void pac_just_move(int dir) {
	pac_x = pac_x + dx1[dir];
	pac_y = pac_y + dy1[dir];
	for (int i = 1; i <= M; i++) {
		monster me = monsters[i];
		if (me.in && me.x == pac_x && me.y == pac_y) { //몬스터 있었다면
			me.die = true;
			me.in = false;
			me.born = false;
			finish[pac_x][pac_y] = global_time + 2; //시체위에 시체...인경우는? 시체 여러개나 한개나 똑같으니까 상관없을듯
			dead[pac_x][pac_y] = 1;
			monsters[me.num] = me;
		}
	}
	board[pac_x][pac_y] = 0;
}

void pac_move() {
	int idx = 0;
	int temp1, temp2;
	int temp_x1, temp_y1;
	int temp_x2, temp_y2;
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++)
			{
				int cur_x = pac_x;
				int cur_y = pac_y; //64번 경우 모두 기존 위치 시작
				int nx = cur_x + dx1[i];
				int ny = cur_y + dy1[i]; //첫번째 전진
				temp1 = board[nx][ny];
				temp_x1 = nx;
				temp_y1 = ny;
				if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) {
					eat[idx] = 0;
					idx++; 
					continue;
				}
				if (board[nx][ny] > 0) {
					eat[idx] += board[nx][ny];
					board[nx][ny] = 0;
				}
				nx = nx + dx1[j];
				ny = ny + dy1[j]; //두번째 전진
				temp2 = board[nx][ny];
				temp_x2 = nx;
				temp_y2 = ny;
				if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) {
					eat[idx] = 0;
					idx++;
					board[temp_x1][temp_y1] = temp1;
					continue;
				}
				if (board[nx][ny] > 0) {
					eat[idx] += board[nx][ny];
					board[nx][ny] = 0;
				}
				nx = nx + dx1[k];
				ny = ny + dy1[k]; //세번째 전진
				if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) {
					eat[idx] = 0;
					idx++;
					board[temp_x1][temp_y1] = temp1;
					board[temp_x2][temp_y2] = temp2;
					continue;
				}
				if (board[nx][ny] > 0) eat[idx] += board[nx][ny];
				board[temp_x1][temp_y1] = temp1;
				board[temp_x2][temp_y2] = temp2;
				idx++;
			}
		}
	}

	idx = 0;
	int max_eat = -1; //아무것도 못먹는 경우 
	int dir_1, dir_2, dir_3;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++)
			{
				if (eat[idx] > max_eat) {
					max_eat = eat[idx];
					dir_1 = i;
					dir_2 = j;
					dir_3 = k;
				}
				idx++;
			}
		}
	}
	pac_just_move(dir_1);
	pac_just_move(dir_2);
	pac_just_move(dir_3);
}
void monster_born() {
	for (int i = 1; i <= M; i++) {
		monster me = monsters[i];
		if (me.born == true) {
			me.born = false;
			me.in = true;
			board[me.x][me.y]++;
			monsters[me.num] = me;
		}
	}
}


void remove_dead() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (finish[i][j] == global_time) {
				dead[i][j] = 0;
			}
		}
	}
}

int main() {
	cin >> M >> T;
	cin >> pac_x >> pac_y;
	pac_x--;
	pac_y--;
	monsters.push_back({ 0,0,0,0,false,false,true });
	int x, y, d;
	for (int i = 1; i <= M; i++)//M을 써야겠다.
	{
		cin >> x >> y >> d;
		monsters.push_back({i,x-1,y-1,d-1,false,true,false });
		board[x - 1][y - 1]++;
	}
	

	for (global_time = 1; global_time <= T; global_time++)
	{
		int temp_M = M;
		for (int i = 1; i <= temp_M; i++)//M증가해서 꼬일 수 있음
		{
			if (monsters[i].in == true) { //보드내에 존재하는 아이라면
				duplicate(monsters[i]); //복제
			}
		}
		for (int i = 1; i <= temp_M; i++)
		{
			if (monsters[i].in == true) { //보드내에 존재하는 아이라면
				move(monsters[i]); //이동
			}
		}
	

		for (int i = 0; i < 64; i++) {
			eat[i] = 0; //초기화
		}

		remove_dead();
		pac_move();
		monster_born();

	}
	int sum = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			sum += board[i][j];
		}
	}

	cout << sum;
}