팩맨

Simulation

평균 : 180'

---

sol : 197' 06''

• 수행 시간 : 8ms
• 메모리 : 0MB

Learnings

• 너무 비효율적으로 짜는 것만 아니면 수행 시간 문제로 틀리는 건 거의 없을 것.

#include <iostream>
#include <vector>

using namespace std;

#define ALIVE -1

// 상, 좌상, 좌, 좌하, 하, 우하, 우, 우상
int mon_ds[9][2] = { {0, 0}, { -1, 0 }, {-1, -1}, {0, -1}, {1, -1}, { 1, 0 }, {1, 1}, {0, 1}, {-1, 1} };
// 상, 좌, 하, 우
int pack_ds[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };

int turn;

struct Monster {
	int r;
	int c;
	int dir;
	bool isEgg;
	int deadTurn;

	Monster() {}
	Monster(int _r, int _c, int _dir, bool _isEgg, int _deadTurn) :
		r(_r), c(_c), dir(_dir), isEgg(_isEgg), deadTurn(_deadTurn) {
	}
};

struct PackMan {
	int r;
	int c;

	PackMan() {}
	PackMan(int _r, int _c) :
		r(_r), c(_c) {
	}
};

int m, t;
PackMan packMan;
vector<Monster> monsters;
vector<int> packManMoves;
int curEatMons, bestEatMons;
int bestEatDirs[3];

int deadMonsTurnGrid[5][5];
int aliveMonsNumGrid[5][5];

bool InGrid(int i, int j) {
	return 1 <= i && i <= 4 && 1 <= j && j <= 4;
}

void Init() {
	cin >> m >> t;

	int pr, pc;
	cin >> pr >> pc;
	packMan = PackMan(pr, pc);

	for (int i = 1; i <= m; i++) {
		int mr, mc, md;
		cin >> mr >> mc >> md;
		monsters.push_back(Monster(mr, mc, md, false, ALIVE));
		aliveMonsNumGrid[mr][mc]++;
	}
}

void TryDuplicate() {
	for (int mons = 0; mons < monsters.size(); mons++) {
		if (monsters[mons].deadTurn != ALIVE || monsters[mons].isEgg) continue;

		monsters.push_back(Monster(monsters[mons].r, monsters[mons].c, monsters[mons].dir, true, ALIVE));
	}
}

bool DeadMonsExist(int r, int c) {
	return (deadMonsTurnGrid[r][c] >= turn);
}

void MonsMove() {
	for (int mons = 0; mons < monsters.size(); mons++) {
		// 알 상태이거나 죽은 몬스터는 움직이지 않는다.
		if (monsters[mons].isEgg || monsters[mons].deadTurn != ALIVE) continue;

		int ni = monsters[mons].r + mon_ds[monsters[mons].dir][0];
		int nj = monsters[mons].c + mon_ds[monsters[mons].dir][1];

		int dirCnt = 0;
		bool canMove = true;
		// 그리드 밖이거나 죽은 시체가 있거나 팩맨이 있을 경우 반시계 45도 방향 전환
		while (!InGrid(ni, nj) || DeadMonsExist(ni, nj) > 0 || packMan.r == ni && packMan.c == nj) {
			monsters[mons].dir = (monsters[mons].dir + 1 > 8) ? 1 : monsters[mons].dir + 1;
			ni = monsters[mons].r + mon_ds[monsters[mons].dir][0];
			nj = monsters[mons].c + mon_ds[monsters[mons].dir][1];
			dirCnt++;
			if (dirCnt >= 8) {
				canMove = false;
				break;
			}
		}
		if (!canMove) continue;
		aliveMonsNumGrid[monsters[mons].r][monsters[mons].c]--;
		monsters[mons].r = ni, monsters[mons].c = nj;
		aliveMonsNumGrid[monsters[mons].r][monsters[mons].c]++;
	}
}

int PackManEachMove() {
	int tempPM_r = packMan.r, tempPM_c = packMan.c;
	int aliveMonsNum = 0;
	int tempAliveMonsNumGrid[5][5];
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			tempAliveMonsNumGrid[i][j] = aliveMonsNumGrid[i][j];
		}
	}

	for (int i = 0; i < 3; i++) {
		int ni = tempPM_r + pack_ds[packManMoves[i]][0];
		int nj = tempPM_c + pack_ds[packManMoves[i]][1];

		if (!InGrid(ni, nj)) return -1;
		aliveMonsNum += tempAliveMonsNumGrid[ni][nj];
		tempAliveMonsNumGrid[ni][nj] = 0;
		tempPM_r = ni, tempPM_c = nj;
	}

	return aliveMonsNum;
}

void GetPackManBestMove() {
	if (packManMoves.size() == 3) {
		// 일단 이동 가능한 경우를 찾았을 때
		if (bestEatDirs[0] == -1) {
			for (int i = 0; i < 3; i++) bestEatDirs[i] = packManMoves[i];
		}
		//cout << "cur move : ";
		//for (int i = 0; i < 3; i++) cout << packManMoves[i] << ' ';
		curEatMons = PackManEachMove();
		//cout << "cur eat : " << curEatMons << endl;
		if (curEatMons > bestEatMons) {
			bestEatMons = curEatMons;
			for (int i = 0; i < 3; i++) bestEatDirs[i] = packManMoves[i];
		}
		return;
	}

	for (int d = 0; d < 4; d++) {
		packManMoves.push_back(d);
		GetPackManBestMove();
		packManMoves.pop_back();
	}
}

void KillMonsters(int r, int c) {
	for (int i = 0; i < monsters.size(); i++) {
		// 좌표가 같고, 알이 아닌 살아있는 몬스터인 경우
		if (monsters[i].r == r && monsters[i].c == c && monsters[i].deadTurn == ALIVE && !monsters[i].isEgg) {
			monsters[i].deadTurn = turn + 2;
			deadMonsTurnGrid[r][c] = turn + 2;
			aliveMonsNumGrid[r][c] = 0;
		}
	}
}

void PackManMove() {
	for (int i = 0; i < 3; i++) {
		if (bestEatDirs[i] == -1) return;
		int ni = packMan.r + pack_ds[bestEatDirs[i]][0], nj = packMan.c + pack_ds[bestEatDirs[i]][1];
		packMan.r = ni, packMan.c = nj;

		KillMonsters(ni, nj);
	}
}

void RemoveDeadMons() {
	vector<Monster> temp;
	for (int i = 0; i < monsters.size(); i++) {
		if (monsters[i].deadTurn == ALIVE) temp.push_back(monsters[i]);
	}

	monsters = temp;
}

void MonsDupFin() {
	for (int i = 0; i < monsters.size(); i++) {
		if (monsters[i].isEgg) {
			monsters[i].isEgg = false;
			aliveMonsNumGrid[monsters[i].r][monsters[i].c]++;
		}
	}
}

void GetAliveMonsNum() {
	int cnt = 0;
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			cnt += aliveMonsNumGrid[i][j];
		}
	}
	cout << cnt;
}

int main() {
	Init();

	while (++turn <= t) {
		TryDuplicate();

		MonsMove();

		packManMoves.clear();
		bestEatMons = 0;
		for (int i = 0; i < 3; i++) bestEatDirs[i] = -1;
		GetPackManBestMove();;
		PackManMove();

		RemoveDeadMons();

		MonsDupFin();
	}
	GetAliveMonsNum();

	return 0;
}