문제 링크

삼성 코딩테스트 기출 문제: 미로 타워 디펜스 | 코드트리

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

코드트리

문제 설명

n*n으로 이루어진 나선형 미로에 1,2,3의 몬스터가 있음. 중간에는 플레이어가 있음.

1턴 당 다음과 같은 절차들이 실행됨.

1. 플레이어가 상하좌우 방향 중 주어진 공격 칸 만큼 몬스터를 공격해서 없앰 → 점수에 추가
2. 빈 공간은 뒤 몬스터들이 채움
3. 종류가 같은 몬스터가 4번 이상 반복되면 삭제 → 점수에 추가
4. 3번을 해결했는데도 또 4번 이상 반복되는 몬스터가 있으면 삭제
5. 몬스터들을 각각 (총 개수, 숫자의 크기)로 변환해서 다시 미로속에 집어넣음

해결 방법

몬스터를 문제에서 설명해준 대로 설정함.

void set_new_monster() {
	vector<int> new_monster;
	for (int i = 0;i < monster.size();i++) {
		int cnt = 0;
		for (int j = i;j < monster.size();j++) {
			if (monster[i] == monster[j]) cnt++;
			else break;
		}

		new_monster.push_back(cnt);
		new_monster.push_back(monster[i]);

		if (cnt > 1) {
			i += cnt - 1;
		}
	}
	if (new_monster.size() > idx_arr.size()) {
		new_monster.resize(idx_arr.size());
	}
	monster = new_monster;
}

중복된 몬스터 삭제몬스터들을 순회하면서, 4번 이상 반복된 몬스터들을 표시함.

bool delete_duplicate() {
	bool ret = false;

	for (int i = 0;i < monster.size()-1;i++) {
		int cnt = 1;
		for (int j = i+1;j < monster.size();j++) {
			if (monster[i] == monster[j]) cnt++;
			else break;
		}

		if (cnt >= 4) {
			ret = true;
			score += cnt * monster[i];
			for (int j = 0;j < cnt;j++) {
				monster[i + j] = -1;
			}
			i += (cnt-1);
		}
	}

	return ret;
}

표시된 몬스터들을 제거함.

void erase_remove() {
	vector<int> new_monster;
	for (int i = 0;i < monster.size();i++) {
		if (monster[i] != -1) {
			new_monster.push_back(monster[i]);
		}
	}
	
	monster = new_monster;
}

더이상 표시된 몬스터가 없으면 해당 반복문을 탈출.

플레이어 공격attack_arr 배열에 플레이어가 공격한 위치를 표시함.

void player_attack(int d,int p) {
	memset(attack_arr, 0, sizeof(attack_arr));
	int x, y;
	x = n / 2, y = n / 2;
	
	for (int i = 0;i < p;i++) {
		x += dx[d], y += dy[d];
		attack_arr[x][y] = 1;
	}
}

몬스터들을 순회하면서 공격한 위치에 있는 몬스터는 제거함.

void set_monster() {
	memset(arr, 0, sizeof(arr));
	int a, b;
	vector<int> new_monster;
	for (int i = 0;i < monster.size();i++) {
		a = idx_arr[i].first, b = idx_arr[i].second;		
		if (attack_arr[a][b] == 0) {
			new_monster.push_back(monster[i]);
		}
		else {
			score += monster[i];
		}
	}
	monster = new_monster;
}

나선형 미로 순서를 벡터에 넣기2차원 배열로 계산하기에는 복잡하니, 벡터로 1차원으로 변환해줌.

void init() {
	int x, y;
	x = n / 2, y = n / 2;

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

	int move = 1;
	int dir = 0;
	int cnt = 0;
	while (true) {
		for (int i = 0;i < move;i++) {
			x += dtx[dir], y += dty[dir];
			if (arr[x][y] != 0) monster.push_back(arr[x][y]);
			idx_arr.push_back({ x,y });
			if (x == 0 && y == 0) break;
		}
		if (x == 0 && y == 0) break;
		dir = (dir + 1) % 4;
		cnt++;
		if (cnt == 2) {
			move++;
			cnt = 0;
		}
	}
}

전체 코드

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

int n, m;

int arr[26][26];
vector<pair<int, int>> attack;
vector<pair<int, int>> idx_arr;
vector<int> monster;

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

int attack_arr[26][26];

int score = 0;

void input() {
	cin >> n >> m;

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0;i < m;i++) {
		int d, p;
		cin >> d >> p;
		attack.push_back({ d,p });
	}
}

void init() {
	int x, y;
	x = n / 2, y = n / 2;

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

	int move = 1;
	int dir = 0;
	int cnt = 0;
	while (true) {
		for (int i = 0;i < move;i++) {
			x += dtx[dir], y += dty[dir];
			if (arr[x][y] != 0) monster.push_back(arr[x][y]);
			idx_arr.push_back({ x,y });
			if (x == 0 && y == 0) break;
		}
		if (x == 0 && y == 0) break;
		dir = (dir + 1) % 4;
		cnt++;
		if (cnt == 2) {
			move++;
			cnt = 0;
		}
	}
}

void player_attack(int d,int p) {
	memset(attack_arr, 0, sizeof(attack_arr));
	int x, y;
	x = n / 2, y = n / 2;
	
	for (int i = 0;i < p;i++) {
		x += dx[d], y += dy[d];
		attack_arr[x][y] = 1;
	}
}

void set_monster() {
	memset(arr, 0, sizeof(arr));
	int a, b;
	vector<int> new_monster;
	for (int i = 0;i < monster.size();i++) {
		a = idx_arr[i].first, b = idx_arr[i].second;		
		if (attack_arr[a][b] == 0) {
			new_monster.push_back(monster[i]);
		}
		else {
			score += monster[i];
		}
	}
	monster = new_monster;
}

bool delete_duplicate() {
	bool ret = false;

	for (int i = 0;i < monster.size()-1;i++) {
		int cnt = 1;
		for (int j = i+1;j < monster.size();j++) {
			if (monster[i] == monster[j]) cnt++;
			else break;
		}

		if (cnt >= 4) {
			ret = true;
			score += cnt * monster[i];
			for (int j = 0;j < cnt;j++) {
				monster[i + j] = -1;
			}
			i += (cnt-1);
		}
	}

	return ret;
}

void erase_remove() {
	vector<int> new_monster;
	for (int i = 0;i < monster.size();i++) {
		if (monster[i] != -1) {
			new_monster.push_back(monster[i]);
		}
	}
	
	monster = new_monster;
}

void set_new_monster() {
	vector<int> new_monster;
	for (int i = 0;i < monster.size();i++) {
		int cnt = 0;
		for (int j = i;j < monster.size();j++) {
			if (monster[i] == monster[j]) cnt++;
			else break;
		}

		new_monster.push_back(cnt);
		new_monster.push_back(monster[i]);

		if (cnt > 1) {
			i += cnt - 1;
		}
	}
	if (new_monster.size() > idx_arr.size()) {
		new_monster.resize(idx_arr.size());
	}
	monster = new_monster;
}

void solve(int idx) {
	player_attack(attack[idx].first, attack[idx].second);
	set_monster();
	while (1) {
		if (delete_duplicate() == false) break;
		erase_remove();
	}
	set_new_monster();
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("sample_input.txt", "r", stdin);
	input();
	init();

	for (int i = 0;i < m;i++) {
		solve(i);
	}
	cout << score;
}