[백준 21611번 - 마법사 상어와 블리자드] C++ 풀이

https://www.acmicpc.net/problem/21611

21611번: 마법사 상어와 블리자드

 

이 문제 덕분에 구현력이 한층 상승한 기분..

전체적인 나의 전략은 아래의 그림과 같다.

2차원의 map을 입력받아 저장하고, 구슬이 파괴되는 부분의 map 값을 -1로 만들어 주어 파괴되었음을 표시했다.

그 다음에는 달팽이 모양을 따라서 1차원의 배열로 펼친다. 그래야 같은 구슬이 4개 이상 연속하는지 검사하여 구슬을 폭파시킬 수 있다.

이때 주의할 점은, 4개 이상 모여있는 구슬을 만나면 바로 폭파시키면 안된다. 문제를 잘 읽어야 하는게, 한번 처음부터 끝까지 배열을 검사하여 4개 이상 모여있는 그룹들을 파악하고, 이를 한번에 폭파시켜야 한다. (이렇게 하지 않으면 틀린 결과가 나오는 TC가 존재한다.)

이 점에 대한 처리가 좀 어려웠는데.. 1차원 배열을 순회하면서 폭파하는 구슬을 제외하고 나머지 구슬만 복사해주었다.  그 다음에 다 폭파시켰으면 이제 구슬을 변화시켜야 한다. 1차원 배열을 차례대로 순회하면서 구슬의 갯수와 종류를 세어 새로운 배열에 넣어준다. 다 끝나면 새로운 배열을 다시 원래 배열에 복사해준다. 해당 1차원 배열은 다시 2차원 배열 map에 저장해준다. 그리고 이러한 과정을 m번 반복하며 시행한다.

 

 

처음에는 vector 의 erase를 사용하여 구현했었다. map의 0인 값은 버리고, 1차원 vector에 저장해주었고, 폭파 시킨 구슬은 erase시켰다. erase할때 index 가 변하기 때문에 지울때도 뒤에서부터 순회하며 지웠다. 구슬을 변화시킬때는 새로운 vector를 만들어서 값을 채워주고 원래 vector에 복사하였다. 근데 이렇게 해서 이것저것 Test 해봤을때 답이 잘 나왔는데 계속 5%에서 틀렸습니다가 떴다. 꼬박 하루동안 고민했지만 어디가 틀렸는지 도무지 모르겠더라... 시험장에서는 이렇게 위험한 erase를 쓰기보다는 문제에 주어진 그대로 최대한 구현하는 것이 답이라고 생각이 들었고, 다시 처음부터 코드를 짰다. 문제에 있는 그대로. 2차원 map -> 1차원 arr 로 바꿀때도 0을 포함한 모든 값을 넣어 주었고, 구슬이 폭파할 때에도 줄어든 만큼 뒤에 0을 잘 채워주었다. 다시 1차원 arr -> 2차원 map 할때도 그대로. 이렇게 하니까 맞았습니다가 떴다. 확실히 vector로 했을때는 공간복잡도가 좀 적었겠지만, n * n 사이즈 제한이 있어서 해당 부분을 제어해주는 것이 까다로웠다. 처음 접근이 아마 해당 부분에서 뭔가 잘못되어서 틀렸지 않았을까 싶다.

절대 절대 시험장 가서는 특히 구현이라면 효율이니 뭐니 따지기 보다 문제에 있는 그대로. 코드로 옮기자. erase는 가급적 사용을 지양하고 새로운 배열을 만들어 copy하는 방식을 사용하자.

 

완성 코드는 다음과 같다.

#include <stdio.h>
#include <vector>

using namespace std;
int m, n;
int MAP[50][50];
int snail[50][50];
int indexValue[2500];
int dx[] = {0, 1, 0, -1, 0};
int dy[] = {-1, 0, 1, 0, -1};

int tx[] = {0, -1, 1, 0, 0};
int ty[] = {0, 0, 0, -1, 1};

int startX, startY;
int icnt;
int one_cnt = 0;
int two_cnt = 0;
int three_cnt = 0;

void makeArr(int map[50][50], int arr[]) { // 2차원 -> 1차원
	int h[] = {1, 1, 2, 2, 2};
	int cnt = n / 2;
	bool flag = false;
	int idx = 0;
	int nx = startX;
	int ny = startY;
	int ncnt = 1;
	indexValue[idx++] = MAP[nx][ny];
	for(int i = 0; i < cnt; ++i) {
		for(int j = 0; j < 5; ++j) {
			for(int k = 0; k < h[j]; ++k) {
				nx = nx + dx[j];
				ny = ny + dy[j];
				if (MAP[nx][ny] != -1) {
				    indexValue[idx++] = MAP[nx][ny];
                    ncnt++;
                }
			}
			if (flag)
				break;
		}
		if (flag)
			break;
		for(int j = 1; j < 5; ++j) {
			h[j] += 2;
		}
	}
    for (int i = ncnt; i < n * n; ++i) {
        indexValue[i] = 0;
    }
}

void makeMap(int arr[]) { // 1차원 -> 2차원
	int new_arr[2500] = {0};
	int ncnt, count;
	ncnt = 1;
	count = 1;
	for(int i = 1; i < icnt; ++i) {
		if (arr[i] == arr[i + 1])
			count++;
		else {
			new_arr[ncnt++] = count;
			new_arr[ncnt++] = arr[i];
			count = 1;
		}
		if (ncnt == n * n)
			break;
	}
	for(int i = 1; i < ncnt; ++i) {
		arr[i] = new_arr[i];
	}
	for(int i = ncnt; i < n * n; ++i) {
		arr[i] = 0;
	}

	int h[] = {1, 1, 2, 2, 2};
	int cnt = n / 2;
	bool flag = false;
	int idx = 0;
	int nx = startX;
	int ny = startY;
	MAP[nx][ny] = indexValue[idx++];
	for(int i = 0; i < cnt; ++i) {
		for(int j = 0; j < 5; ++j) {
			for(int k = 0; k < h[j]; ++k) {
				nx = nx + dx[j];
				ny = ny + dy[j];
				MAP[nx][ny] = indexValue[idx++];
			}
			if (flag)
				break;
		}
		if (flag)
			break;
		for(int j = 1; j < 5; ++j) {
			h[j] += 2;
		}
	}
}

int explode(int arr[]) {
	int flag, count, start, tcnt;

	flag = 0;
	start = count = 1;

	tcnt = n * n;
	icnt = 1;
	for(int i = 1; i < tcnt; ++i) {
		if (arr[i] == arr[i + 1])
			count++;
		else {
			if (count < 4) {
				for(int k = start; k < start + count; ++k) {
					arr[icnt++] = arr[k];
				}
			} else {
				if (arr[i] == 1)
					one_cnt += count;
				else if (arr[i] == 2)
					two_cnt += count;
				else
					three_cnt += count;
				flag = 1;
			}
			start = i + 1;
			count = 1;
		}
	}

	for(int i = icnt; i < tcnt; ++i) {
		arr[i] = 0;
	}
	return flag;
}

int main() {
	scanf("%d %d", &n, &m);

	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			scanf("%d", &MAP[i][j]);
		}
	}

	startX = (n + 1) / 2;
	startY = (n + 1) / 2;

	for(int i = 0; i < m; ++i) {
		int d, s;
		scanf("%d %d", &d, &s);

		int nx, ny;
		for(int k = 1; k <= s; ++k) {
			nx = startX + tx[d] * k;
			ny = startY + ty[d] * k;
			MAP[nx][ny] = -1; // 구슬 파괴
		}

		makeArr(MAP, indexValue); // 2차원 -> 1차원

		// 구슬 폭발
		while(true) {
			int result = explode(indexValue);
			if (result == 0)
				break;
		}

		makeMap(indexValue); // 1차원 -> 2차원

	}
	printf("%d\n", one_cnt + two_cnt * 2 + three_cnt * 3);
	return 0;
}