문제 링크

삼성 코딩테스트 기출 문제: 팩맨 - 코드트리

주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.

코드트리

문제 설명

4*4 격자에 m개의 몬스터와 1개의 팩맨이 주어짐. 각각의 몬스터는 상하좌우, 대각선 방향 중 하나를 가짐. 게임의 턴은 다음과 같음

1. 몬스터 복제 시도현재 위치에 자신과 같은 방향을 가진 몬스터를 복제함. 다음 턴에 깨어남.
2. 몬스터 이동몬스터가 이동함. 움직이려는 칸에 시체가 있거나, 팩맨이 있거나, 격자를 벗어나면 반시계 방향으로 45도 회전함. 만약 갈 수 없다면, 가능할 때까지 반시계방향으로 45도 회전하고, 움직일 수 없으면 움직이지 않음.
3. 팩맨 이동총 3칸 이동하는데, 상-좌-하-우의 우선순위를 가지며 몬스터를 가장 많이 먹는 곳으로 감.
4. 몬스터 시체 소멸몬스터가 죽으면 시체가 생김. 시체는 2턴동안 유지됨.
5. 몬스터 복제 완성알이 부화함

해결 방법

팩맨 이동 및 몬스터 먹기

	int dtx[4] = { -1,0,1,0 };
	int dty[4] = { 0,-1,0,1 };

	int x1, x2, x3, y1, y2, y3;
	x1 = r + dtx[d1], y1 = c + dty[d1];
	x2 = x1 + dtx[d2], y2 = y1 + dty[d2];
	x3 = x2 + dtx[d3], y3 = y2 + dty[d3];
	r = x3, c = y3;
	int mx, my, md;
	for (int i = 0;i < monster.size();i++) {
		tie(mx, my, md) = monster[i];
		if ((mx == x1 && my == y1) || (mx == x2 && my == y2) || (mx == x3 && my == y3)) {
			dead_body[mx][my] = 3;
		}
		else {
			next_monster.push_back({ mx,my,md });
		}
	}

팩맨 움직일 위치 정하기

	int d1, d2, d3;
	int val = -1;
	for (int i = 0;i < 4;i++) {
		for (int j = 0;j < 4;j++) {
			for (int k = 0;k < 4;k++) {
				int cur = count_monster(i, j, k);
				if (cur > val) {
					val = cur;
					d1 = i, d2 = j, d3 = k;
				}
			}
		}
	}

...

int count_monster(int d1, int d2, int d3) {
	int dtx[4] = { -1,0,1,0 };
	int dty[4] = { 0,-1,0,1 };

	int x1, x2, x3, y1, y2, y3;

	x1 = r + dtx[d1], y1 = c + dty[d1];
	if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= n) return -1;
	x2 = x1 + dtx[d2], y2 = y1 + dty[d2];
	if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= n) return -1;
	x3 = x2 + dtx[d3], y3 = y2 + dty[d3];
	if (x3 < 0 || x3 >= n || y3 < 0 || y3 >= n) return -1;

	int mx, my, md;
	int ret = 0;
	for (int i = 0;i < monster.size();i++) {
		tie(mx, my, md) = monster[i];
		if ((mx == x1 && my == y1) || (mx == x2 && my == y2) || (mx == x3 && my == y3)) {
			ret++;
		}
	}
	return ret;
}

몬스터 이동

void monster_move(int t) {
	int x, y, d;
	tie(x, y, d) = monster[t];

	int nx, ny,nd;
	for (int i = 0;i < 8;i++) {
		nd = (d + i) % 8;
		nx = x + dx[nd];
		ny = y + dy[nd];

		if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
		if (nx == r && ny == c) continue;
		if (dead_body[nx][ny] > 0) continue;
		
		monster[t] = make_tuple(nx, ny, nd);
		break;
	}
}

몬스터 복제 시도턴이 종료한 후 넣을 몬스터들을 넣어줌.

void make_egg() {
	vector<tuple<int, int, int>> tmp;
	for (int i = 0;i < monster.size();i++) {
		tmp.push_back(monster[i]);
	}
	next_monster = tmp;
}

전체 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;

int n;
int m, t;
int r, c;
vector<tuple<int, int, int>> monster;
vector<tuple<int, int, int>> next_monster;

int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,-1,-1,-1,0,1,1,1 };

int dead_body[5][5];

void input() {
	cin >> m >> t;
	cin >> r >> c;

	int x, y, z;
	for (int i = 0;i < m;i++) {
		cin >> x >> y >> z;
		monster.push_back({ x-1,y-1,z-1 });
	}

	n = 4;
	r -= 1; c -= 1;
}

void make_egg() {
	vector<tuple<int, int, int>> tmp;
	for (int i = 0;i < monster.size();i++) {
		tmp.push_back(monster[i]);
	}
	next_monster = tmp;
}

void monster_move(int t) {
	int x, y, d;
	tie(x, y, d) = monster[t];

	int nx, ny,nd;
	for (int i = 0;i < 8;i++) {
		nd = (d + i) % 8;
		nx = x + dx[nd];
		ny = y + dy[nd];

		if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
		if (nx == r && ny == c) continue;
		if (dead_body[nx][ny] > 0) continue;
		
		monster[t] = make_tuple(nx, ny, nd);
		break;
	}
}

int count_monster(int d1, int d2, int d3) {
	int dtx[4] = { -1,0,1,0 };
	int dty[4] = { 0,-1,0,1 };

	int x1, x2, x3, y1, y2, y3;

	x1 = r + dtx[d1], y1 = c + dty[d1];
	if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= n) return -1;
	x2 = x1 + dtx[d2], y2 = y1 + dty[d2];
	if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= n) return -1;
	x3 = x2 + dtx[d3], y3 = y2 + dty[d3];
	if (x3 < 0 || x3 >= n || y3 < 0 || y3 >= n) return -1;

	int mx, my, md;
	int ret = 0;
	for (int i = 0;i < monster.size();i++) {
		tie(mx, my, md) = monster[i];
		if ((mx == x1 && my == y1) || (mx == x2 && my == y2) || (mx == x3 && my == y3)) {
			ret++;
		}
	}
	return ret;
}

void pacman_move() {
	int d1, d2, d3;
	int val = -1;
	for (int i = 0;i < 4;i++) {
		for (int j = 0;j < 4;j++) {
			for (int k = 0;k < 4;k++) {
				int cur = count_monster(i, j, k);
				if (cur > val) {
					val = cur;
					d1 = i, d2 = j, d3 = k;
				}
			}
		}
	}

	int dtx[4] = { -1,0,1,0 };
	int dty[4] = { 0,-1,0,1 };

	int x1, x2, x3, y1, y2, y3;
	x1 = r + dtx[d1], y1 = c + dty[d1];
	x2 = x1 + dtx[d2], y2 = y1 + dty[d2];
	x3 = x2 + dtx[d3], y3 = y2 + dty[d3];
	r = x3, c = y3;
	int mx, my, md;
	for (int i = 0;i < monster.size();i++) {
		tie(mx, my, md) = monster[i];
		if ((mx == x1 && my == y1) || (mx == x2 && my == y2) || (mx == x3 && my == y3)) {
			dead_body[mx][my] = 3;
		}
		else {
			next_monster.push_back({ mx,my,md });
		}
	}
}

void solve() {
	make_egg();
	
	for (int i = 0;i < monster.size();i++) {
		monster_move(i);
	}

	pacman_move();

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (dead_body[i][j] > 0) dead_body[i][j]--;
		}	
	}
	monster = next_monster;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	freopen("sample_input.txt", "r", stdin);
	input();
	for (int i = 0;i < t;i++) {
		solve();
	}
	
	cout << monster.size();
}