코드트리 미로 타워 디펜스 C++

문제는 시뮬레이션 문제이다.

 

1. 

삼성 문제는 몇가지 유형으로 나뉜다.

시뮬레이션 문제 역시 몇가지 유형으로 나뉘는 것 같다.

1. 도형 이동 시키는 문제

2. 회전하는 좌표

3. 단순 빡구현

물론 1, 2번도 단순 구현이 많이 있는 편이다.

 

기출문제를 풀다보니 몇가지 요령이 생겼다.

1. 여러가지 함수로 나누어서 풀 것 

이렇게 모듈화를 시키니 나중에 디버깅하기도 편리하고 재사용이 편리하다

2. 푸는 도중에 계속해서 디버깅 할 것

모듈화해서 풀고 각각의 모듈이 완성될 때마다 디버깅을 하니 나중에 디버깅 할 양도 줄어들고 중간 중간에 문제를 위해 최적화를 할 방안을 생각하기가 쉽다.

 

2. 이 문제는 2번 유형에 해당한다. 

 

내가 풀이한 방식은, 배열에 다음에 이동해야할 방향을 담았다. 

처음에는 (0,0)부터 (n/2, n/2)로 가는 역방향 배열을 만들었는데 문제를 풀어보니 역방향으로는 풀이가 어려워서 정방향으로 풀었다.

 

역방향 코드는 아래와 같다.

 

   while (x != n / 2 || y != n / 2) {
      int ny = y + dy[dir];
      int nx = x + dx[dir];
      if (!inRange(nx, ny) || dirArr[ny][nx] != -1) {
         dir = (dir + 1) % 4;
      }
      dirArr[y][x] = dir;
      y = y + dy[dir];
      x = x + dx[dir];
   }

 

정방향 코드는 아래와 같다.

 

while (1) {
		if (arr[y][x] == 0 || (x==0 && y==0)) {
			break;
		}
		if (arr[y][x] != -1) {
			v.push_back(arr[y][x]);
		}
		dir = dirArr[y][x];
		x = x + dx[dir];
		y = y + dy[dir];
	}
}

그리고 각각 방향을 보며 그 다음에 가야할 좌표를 알 수 있다.

그리고 한번 삭제를 하고 나면 벡터에 가야하는 숫자들을 모두 담아서 문제를 풀었다.

벡터를 사용해서 좌표계에 옮긴다라는 개념을 가지고 풀면 쉽게 풀 수 있는 문제였다.

자세한 설명은 아래에 담았다.

 

 

디버깅의 경우 처음에 있었던 문제는 새로운 배열을 만들었을 때 격자의 범위를 넘는 것이었다. 이는 쉽게 해결했다. 

두번째 문제는 MakeVector의 종료조건이다. 배열인덱스를 넘어서 참고하는 경우, 그리고 배열 인덱스가 0,0까지 모두 차있는 경우 arr[y][x]==0만으로는 탈출 조건이 부족하다. 이를 참고해서 !(x==0 && y==0) 으로 변경했다. 

 

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

using namespace std;

#define MAX_N 26

int n, m, d, p;
int score;

int arr[MAX_N][MAX_N];
int dirArr[MAX_N][MAX_N];

int dx[4] = { 1, 0, -1, 0 }; // 오른쪽 아래 왼쪽 위 
int dy[4] = { 0, 1, 0, -1 };

bool inRange(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < n;
}

int changeDir(int x) {
	if (x != 0) {
		return x - 1;
	}
	else {
		return 3;
	}
}

void mapDir() {
	int x = n / 2, y = n / 2, dir = 2;
	dirArr[y][x] = dir;
	int count = 1;
	while (1) {
		int iter = count;
		for (int i = 0;i < iter;i++) {
			dirArr[y][x] = dir;
			y = y + dy[dir];
			x = x + dx[dir];
		}
		if (count == n) {
			break;
		}
		dir = changeDir(dir);
		for (int i = 0;i < iter;i++) {
			dirArr[y][x] = dir;
			y = y + dy[dir];
			x = x + dx[dir];
		}
		dir = changeDir(dir);
		count++;
	}
}

void Delete() {
	int x = n / 2, y = n / 2;
	for (int i = 0;i < p;i++) {
		x = x + dx[d];
		y = y + dy[d];
		score += arr[y][x];
		arr[y][x] = -1; // 지운다
	}
}

void MakeVector(vector<int>& v) {
	int x = n / 2, y = n / 2;
	int dir = dirArr[y][x];
	y = y + dy[dir];
	x = x + dx[dir];
	while (1) {
		if (arr[y][x] == 0 || (x==0 && y==0)) {
			break;
		}
		if (arr[y][x] != -1) {
			v.push_back(arr[y][x]);
		}
		dir = dirArr[y][x];
		x = x + dx[dir];
		y = y + dy[dir];
	}
}

void MoveUp(vector<int> v) {
	int x = n / 2, y = n / 2;
	int dir = dirArr[y][x];
	y = y + dy[dir];
	x = x + dx[dir];
	memset(arr, 0, sizeof(arr));
	for (int i = 0;i < v.size() && i < n*n;i++) {
		arr[y][x] = v[i];
		dir = dirArr[y][x];
		x = x + dx[dir];
		y = y + dy[dir];
	}
}

int Erase(vector<int> &v) {
	int should_stop = 0;
	int st = 0, end;
	vector<int> tmp;
	while (st < v.size()) {
		int flag = 0;
		if (st + 3 < v.size()) {
			if (v[st] == v[st + 1] && v[st] == v[st + 2] && v[st] == v[st + 3]) {
				should_stop = 1;
				flag = 1;
			}
			end = st + 3;
			if (flag == 1) {
				while (end < v.size() && v[st] == v[end]) {
					end++;
				}
				for (int i = st;i < end;i++) {
					score += v[i];
				}
				st = end; continue;
			}
		}
		tmp.push_back(v[st]);
		st++;
	}
	v = tmp;
	if (should_stop == 0) {
		return 1;
	}
	else {
		return 0;
	}
}
void MakeMaze(vector<int>& v) {
	int st = 0, end;
	vector<int> tmp;
	while (st != v.size()) {
		end = st + 1;
		while (end < v.size() && v[st] == v[end]) {
			end++;
		}
		int count = end - st;
		tmp.push_back(count);
		tmp.push_back(v[st]);
		st = end;
	}
	v = tmp;
}
void round(void) {
	vector<int> v;
	// 몬스터를 없앤다
	Delete();
	// 없앤 후 남은 몬스터들의 배열을 만든다
	MakeVector(v);
	while (1) { // 벡터를 기반으로 4개 연속한 경우 삭제하고 변화가 없을 때까지 다시 백터 만들기를 반복한다
		if (Erase(v)) break;
	}
	MakeMaze(v);
	MoveUp(v);
//	cout << "hi" << endl;
}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> arr[i][j];
		}
	}

	mapDir(); // 방향을 표시한다
	for (int i = 0;i < m;i++) {
		cin >> d >> p;
		round();
	}
	cout << score << endl;
	return 0;
}