[코드트리] 팩맨

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

💻 문제 풀이 : C++

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

struct Unit
{
	int r, c, d;
};

int M, T, R, C;

// 현재 맵 몬스터 수
int Grid[6][6];
// 현재 맵 시체 상태
int dead[6][6];

int zeroFlag;

Unit pm;
vector<Unit> mn;
// 다음 몬스터
vector<Unit> nmn;

// 이번턴에 삭제할 후보 좌표
vector<Unit> cmn;
// 이번턴에 삭제할 진짜 좌표
vector<Unit> dmn;

// ↑, ↖, ←, ↙, ↓, ↘, →, ↗
int dr[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc[] = {0, -1, -1, -1, 0, 1, 1, 1};

int cnt;

int inRange(int r, int c)
{
	if (r <= 0 || c <= 0 || r > 4 || c > 4) return 0;
	return 1;
}

int rotate45(int d)
{
	return (d + 1) % 8;
}

int isDeadMan(int r, int c)
{
	if(dead[r][c] != 0) return 1;
	else return 0;
}

int isPackMan(int r, int c)
{
	if (r == pm.r &&
		c == pm.c)
		return 1;
	else return 0;
}

int sim(vector<int> s)
{
	int visited[6][6] = { 0 };
	int r = pm.r;
	int c = pm.c;
	// int d = pm.d;
	int ans = 0;
	for (int i = 0; i < 3; i++)
	{
		int d = s[i];
		r += dr[d];
		c += dc[d];
		// 겪자 벗어나면 종료
		if (!inRange(r, c)) return 0;
		// 방문 안했으면 팩맨의 개수 세기
		if (visited[r][c] == 0)
		{
			ans += Grid[r][c];
			visited[r][c] = 1;
		}
		// 방향 후보에 기록하기
		cmn.push_back({r, c, d});
	}
	return ans;
}

void dfs(int depth, vector<int> &s)
{
	if (depth == 3)
	{
		cmn.clear();
		int tmp = sim(s);
		// 클 경우 정답후보 초기화
		if (tmp > cnt)
		{
			cnt = tmp;
			dmn = cmn;
		}
		// 한 마리도 못 잡는 경우 우선순위는 방향만!
		else if (tmp == cnt && cnt == 0 && zeroFlag == 0 && cmn.size() == 3)
		{
			dmn = cmn;
			zeroFlag = 1;
		}
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		s.push_back(i * 2);
		dfs(depth + 1, s);
		s.pop_back();
	}
}

void pmmove()
{
	zeroFlag = 0;
	cnt = 0;
	// 방향 3번 고르기
	vector<int> s;
	dfs(0, s);

	// 최대인 경우에서 진짜 움직이기
	for (int k = 0; k < 3; k++)
	{
		int r = dmn[k].r;
		int c = dmn[k].c;
		// 맵에 초기화 해주기
		Grid[r][c] = 0;
		// 마지막에 팩맨 위치 갱신
		if (k == 2)
		{
			pm.r = r;
			pm.c = c;
		}
	}

	// 해당좌표가 아닌경우 nmn에 추가
	for (int i = 0; i < mn.size(); i++)
	{
		int flag = 0;
		int r = mn[i].r;
		int c = mn[i].c;
		for (int k = 0; k < 3; k++)
		{
			if (r == dmn[k].r && c == dmn[k].c)
			{
				flag++;
				// 시체 남기기
				dead[r][c] = 2;
			}
		}
		if (flag == 0)
			nmn.push_back(mn[i]);
	}
}

void mnmove()
{
	// 이동 판단
	for (int i = 0; i < mn.size(); i++)
	{
		int r = mn[i].r;
		int c = mn[i].c;
		int d = mn[i].d;
		// 8방향 탐색
		for (int j = d; j < d + 8; j++)
		{
			int nr = r + dr[j % 8];
			int nc = c + dc[j % 8];
			// 격자 안이고
			// 팩맨이 없고
			// 몬스터 시체가 없고
			if (inRange(nr,nc) && 
				!isPackMan(nr,nc) &&
				!isDeadMan(nr, nc))
			{
				// 이전 Grid 감소
				Grid[r][c] -= 1;

				mn[i].r = nr;
				mn[i].c = nc;
				mn[i].d = j % 8;
			
				// 이동 후 Grid 증가
				Grid[nr][nc] += 1;
				break;
			}
		}
	}
}

// nmn에 넣기
void mncopy()
{
	for (int i = 0; i < mn.size(); i++)
	{
		nmn.push_back(mn[i]);
	}
}

void dbturn()
{
	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			if (dead[i][j] != 0)
				dead[i][j] -= 1;
		}
	}
}

void nmncopy()
{
	memset(Grid, 0, sizeof(Grid));
	for (int i = 0; i < nmn.size(); i++)
		Grid[nmn[i].r][nmn[i].c] += 1;
	mn = nmn;
	nmn.clear();
}

void dbclear()
{
	
}

void CLEAR()
{

}

void INPUT()
{
	cin >> M >> T;
	cin >> R >> C;
	pm = { R, C };
	for (int i = 0; i < M; i++)
	{
		int r, c, d;
		cin >> r >> c >> d;
		mn.push_back({ r, c, d-1 });
		Grid[r][c] += 1;
	}
}

void SOLVE()
{
	int time = 0;
	while (time < T)
	{
		// 몬스터 복제 시도
		mncopy();
		// 몬스터 이동
		mnmove();
		// 시체 턴 감소
		dbturn();
		// 팩맨 이동
		pmmove();
		// 몬스터 시체 소멸
		dbclear();
		// 몬스터 새로 복제
		nmncopy();
		time++;
	}
	cout << mn.size() << endl;
}

int main()
{
	CLEAR();
	INPUT();
	SOLVE();

	return 0;
}

📌 memo 😊