백준 21611 마법사 상어와 블리자드

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

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

 

- (빡!)구현 문제이다. 시간복잡도는 블리자드 연산에 N^2 + 총 M번 명령이 수행되므로 O(MN^2)이다.

 

- 이 문제는 초기 접근법이 중요하다. 초기 접근법에 따라 코드 설계 난이도가 달라진다. 먼저, 풀이 과정으로는

 

1. 상어 칸부터 시작해서 맨 마지막 칸 까지의 좌표를 순서대로 map_xy에 담는다. 해당 로직은 all_xy 함수에서 실행된다. move 변수는 주어진 방향으로 총 몇 칸을 이동할 지를 나타내며, 매 2번의 방향전환마다 move는 1씩 증가한다. 따라서 그에 맞게 이중 for문을 사용하여 구현을 한다. 마지막 칸은 무조건 (0,-1)에 도달하게 되며, 벡터에 담기므로 이 값은 pop_back을 해 준다.

 

2. 마법으로 주어진 방향의 모든 칸을 제거한다. 이는 간단하게 for문을 활용해서 구현하면 된다.

 

3. 이제 빈 칸을 채워야 한다. 여기서, marble_num 벡터를 활용하는데, 해당 벡터에는 상어의 왼쪽 좌표부터 시작하여 끝까지 이동하면서 구슬의 숫자 + 해당 구슬의 연속되는 갯수를 계산하여 벡터에 담는 것이다. 이 때, was_zero 변수를 잘 활용한다.

 

- 나올 수 있는 경우의 수는

 

 

1) 현재 값이 0이었고 다음 값도 0일 때

  => was_zero는 true 상태이고, num_of_same만 ++해주고 넘겨준다.

 

2) 현재 값이 0이었고 다음 값은 0이 아닐 때

  => marble과 num_of_same을 최신화한다. 그리고 was_zero에 false를 대입한다.

 

3) 현재 값이 0이 아니고 다음 값은 0일 때

  => marble과 num_of_same을 벡터에 담는다. 이 후, was_zero를 true로 만든다.

 

4) 현재 값도 0이 아니고 다음 값고 0이 아닐 때

  => 현재 값과 비교해서, 다음 값과 같으면 num_of_same만 ++, 아닌 경우 marble과 num_of_same을 벡터에 담고, marble과 num_of_same을 최신화한다.

 

- 마지막으로, 초기 시작점이 빈칸(0)인 예외처리를 위해 벡터의 처음 값의 구슬이 0인 경우 erase를 해 주고, 마지막에도 0이 담기는 경우 pop_back을 해 준다.

- 또한, 여기까지의 로직이 반복되서 사용되므로 follow_up_marble 함수로 구현을 한다.

- 이 최신화된 marble을 기반으로 map또한 최신화를 시켜준다.

 

4. 다음으로, 폭발이 일어나게 된다. marble의 갯수가 연속으로 4개가 넘는 벡터 요소를 제거한다. 이 과정에서, 제거되는 벡터를 기반으로 점수를 추가한다. 이 후, 이 marble을 기반으로 map을 최신화한다. 이 후, map이 변화한 상황인데 이 상황은 또 숫자들이 연속되는 정도가 달라진다. 따라서, 다시 한 번 map을 기반으로 marble_num 을 최신화 해 주어야 한다. map을 최신화하는 로직 또한 반복되므로 follow_up_map을 구현했다. 그리고 check_boom을 통해 boom이 계속 일어날 상황인지를 체크하면서 boom()을 계속해서 호출한다.

 

5. 마지막으로, marble_num을 기반으로 다시 맵을 최신화해야한다. 여기서는 index를 0부터 시작해서, 한 칸씩 이동을 하면서 구슬의 번호를 구슬의 갯수만큼 넣어주기만 하면 된다. 단, map을 초과하는 부분은 잘라야 하므로, index를 계속해서 확인하면서 초과 여부를 체크해야 한다. 그와 반대로, 최대 칸까지 도달하지 못하고 끝나는 경우에는 남은 칸을 모두 0으로 만들어준다.

 

- 디버깅까지 거의 3시간이 걸렸다. 초기 모든 이동경로 좌표를 넣는 부분은 이 문제에서 풀어봤어서 쉽게 해결했으나, 경로를 따라 빈 칸을 채우는 과정을 어떻게 구현할 지, 또 그것을 실제로 구현하는 데에서 많이 막혔다. 거기다가 계속해서 marble과 map을 번갈아가며 최신화를 하다보니 머리가 복잡해져서 많이 헤맸다. 2021 삼전 상반기 기출문제였는데, 컷이 빠른 1솔 제출이었던 걸 보면 이 문제를 못 풀었어도 통과는 됐다는 건데.. 실전에선 정말 시간 안에 못 풀 문제라고 생각한다. ㅠㅠ

 

#include <iostream>
#include <vector>
using namespace std;
int dx[] = { 0,1,0,-1 }; int dy[] = { -1,0,1,0 };
int boom_dir_x[] = { -1,1,0,0 }; int boom_dir_y[] = { 0,0,-1,1 };
int n, m, answer;
int dir[100], speed[100];
int map[49][49];
vector<pair<int, int>> map_xy;
vector<pair<int, int>> marble_num;
void debugging() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}
void follow_up_marble() {
	int now_num = map[n / 2][(n / 2) - 1]; int num_of_same = 0;
	bool was_zero = false;
	for (int i = 0; i < map_xy.size(); i++) {
		int x = map_xy[i].first; int y = map_xy[i].second;
		if (was_zero && map[x][y]) {
			now_num = map[x][y]; num_of_same = 1;
			was_zero = false;
		}
		else {
			if (now_num == map[x][y])  num_of_same++;
			else {
				marble_num.push_back({ now_num, num_of_same });
				if (map[x][y] == 0) was_zero = true;
				now_num = map[x][y]; num_of_same = 1;
			}
		}
	}
	marble_num.push_back({ now_num, num_of_same });
	if (marble_num[0].first == 0) marble_num.erase(marble_num.begin());
	if (marble_num[marble_num.size() - 1].first == 0) marble_num.pop_back();
}
void follow_up_map() {
	int index = 0;
	for (int i = 0; i < marble_num.size(); i++) {
		int marble = marble_num[i].first; int num = marble_num[i].second;
		for (int j = 0; j < num; j++) {
			int map_x = map_xy[index].first; int map_y = map_xy[index].second;
			map[map_x][map_y] = marble;
			index++;
		}
	}
	for (int i = index; i < map_xy.size(); i++) map[map_xy[i].first][map_xy[i].second] = 0;
}
void all_xy() { // 상어부터 시작해서 마지막 좌표까지를 map_xy 벡터에 담는다.
	int now_x = n / 2; int now_y = n / 2;
	int move = 1; int direction = 0;
	while (now_y>=0) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < move; j++) {
				now_x += dx[direction]; now_y += dy[direction];
				map_xy.push_back({ now_x, now_y });
			}
			direction = (direction + 1) % 4;
			if (now_y < 0) break;
		}
		move++;
	}
	map_xy.pop_back(); 
}
bool check_boom() {
	for (int i = 0; i < marble_num.size(); i++) {
		if (marble_num[i].second >= 4) return true;
	}
	return false;
}
void boom() {
	// 4개 미만인 요소만 marble_num에 남기고, 4개 이상인 요소들은 모두 제거한다.
	// 제거 과정에서 점수 계산
	vector<pair<int, int>> temp_v;
	for (int i = 0; i < marble_num.size(); i++) {
		if (marble_num[i].second >= 4) {
			answer = answer + marble_num[i].first * marble_num[i].second;
		}
		else temp_v.push_back(marble_num[i]);
	}
	marble_num.clear();
	for (auto a : temp_v) marble_num.push_back(a);
	follow_up_map();
	//최신화 된 map을 기준으로 해서 다시 marble을 최신화
	marble_num.clear();
	follow_up_marble();
}
void change_marble() {
	int index = 0;
	for (int i = 0; i < marble_num.size(); i++) {
		int marble = marble_num[i].first; int num = marble_num[i].second;
		int x = map_xy[index].first; int y = map_xy[index++].second;
		map[x][y] = num;
		if (index == map_xy.size()) break;
		x = map_xy[index].first; y = map_xy[index++].second;
		map[x][y] = marble;
		if (index == map_xy.size()) break;
	}
	for (int i = index; i < map_xy.size(); i++) map[map_xy[i].first][map_xy[i].second] = 0;
}

void push() {
	follow_up_marble();
	// marble 벡터만큼 모든 map 채워놓고, 남은 부분은 모두 0으로 채우기
	follow_up_map();
	// map을 push 했으니, 다시 marble_num을 최신화 한다.
	marble_num.clear();
	follow_up_marble();
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	all_xy();
	for (int i = 0; i < m; i++) {
		cin >> dir[i] >> speed[i];
	}
	for(int i = 0; i < m; i++) { // 마법 시작
		marble_num.clear();
		//폭발 + 빈 칸 채우기
		int d = dir[i]-1; int s = speed[i];
		int shark_x = n / 2; int shark_y = n / 2;
		for (int j = 1; j <= s; j++) {
			int nx = shark_x + (boom_dir_x[d] * j); int ny = shark_y + (boom_dir_y[d] * j);
			map[nx][ny] = 0;
		}
		push();
		while(check_boom()) boom();
		change_marble();
	}
	cout << answer;
	return 0;
}