21609_상어중학교

sol : 113' 04''

• 수행 시간 : 4ms
• 메모리 : 2028KB

Learnings

• 구조체를 복사할 경우 전부 복사하는 값을 줄이기 위해 <utility> 라이브러리의 swap() fn을 사용하면 복사 대신 소유권만 이전하게 된다.

After Optimization

• 수행 시간 : 0ms
• 메모리 : 2028KB

---

• 빨리 풀려고 하다보니 오히려 구현량이 많아지고 계산 횟수가 늘어났다.
• 가장 큰 개선점은 BFS 실행 횟수를 대폭 줄이고, 데이터 정의를 기능별로 세분화하여 구조 자체를 보다 간단하게 줄였다는 점.

After Optimization

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>

using namespace std;

const int MAX_N = 20;
const int BLACK = -1;
const int RAINBOW = 0;
const int EMPTY = -2;
// 상, 하, 좌, 우
const int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

int n, m;
int grid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int tempGrid[MAX_N][MAX_N];
int score;

struct Group {
	int curB;
	// area, rainbowNum, i, j
	tuple<int, int, int, int> stat;
	vector<pair<int, int>> area;

	Group(){}
	Group(int _curB, tuple<int, int, int, int> _stat) :
		curB(_curB), stat(_stat) { }
};

Group largestGroup, curGroup;

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

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

void InitVisited() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = false;
		}
	}
}

void InitTempGrid() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			tempGrid[i][j] = EMPTY;
		}
	}
}

bool InGrid(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < n;
}

void CurrentGroupBfs(int i, int j) {
	queue<pair<int, int>> q;
	tuple<int, int> stdB = { i, j };
	int rainbowCnt = 0;

	curGroup = Group(grid[i][j], make_tuple(1, 0, i, j));
	curGroup.area.push_back({ i, j });

	q.push({ i, j });
	visited[i][j] = true;

	while (!q.empty()) {
		int ci, cj;
		tie(ci, cj) = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];
			if (!InGrid(ni, nj)) continue;
			if (visited[ni][nj]) continue;
			if (grid[ni][nj] == BLACK) continue;

			if (grid[ni][nj] == curGroup.curB) {
				q.push({ ni, nj });
				visited[ni][nj] = true;
				curGroup.area.push_back({ ni, nj });
				if (make_tuple(ni, nj) < stdB) stdB = make_tuple(ni, nj);
			}
			else if (grid[ni][nj] == RAINBOW) {
				q.push({ ni, nj });
				visited[ni][nj] = true;
				curGroup.area.push_back({ ni, nj });
				rainbowCnt++;
			}
		}
	}

	// 무지개 블록 방문 취소 처리
	for (int i = 0; i < curGroup.area.size(); i++) {
		int di = curGroup.area[i].first, dj = curGroup.area[i].second;
		if (grid[di][dj] == RAINBOW) visited[di][dj] = false;
	}
	
	if (curGroup.area.size() >= 2) {
		int stdi, stdj;
		tie(stdi, stdj) = stdB;
		curGroup.stat = make_tuple(curGroup.area.size(), rainbowCnt, stdi, stdj);
		if (curGroup.stat > largestGroup.stat) {
			swap(largestGroup, curGroup);
		}
	}
}

void FindLargestBlockGroup() {
	largestGroup = Group(EMPTY, make_tuple(0, 0, 0, 0));
	InitVisited();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] <= 0 || visited[i][j]) continue;

			CurrentGroupBfs(i, j);
		}
	}
}

void Delete() {
	for (int i = 0; i < largestGroup.area.size(); i++) {
		int di = largestGroup.area[i].first, dj = largestGroup.area[i].second;
		grid[di][dj] = EMPTY;
	}

	int blockCnt = largestGroup.area.size();
	score += blockCnt * blockCnt;
}

void Gravity() {
	int temp_col[MAX_N];
	for (int i = 0; i < n; i++) temp_col[i] = EMPTY;

	for (int j = 0; j < n; j++) {
		for (int i = 0; i < n; i++) temp_col[i] = EMPTY;
		int temp_i = n - 1;

		for (int i = n - 1; i >= 0; i--) {
			if (temp_i < 0) break;
			if (grid[i][j] == EMPTY) continue;
			if (grid[i][j] == BLACK) {
				temp_col[i] = BLACK;
				temp_i = i - 1;
			}
			if (grid[i][j] >= 0) {
				temp_col[temp_i] = grid[i][j];
				temp_i--;
			}
		}

		for (int i = 0; i < n; i++) {
			grid[i][j] = temp_col[i];
		}
	}
}

void DupGrid(int from[MAX_N][MAX_N], int to[MAX_N][MAX_N]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void Rotate() {
	InitTempGrid();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			tempGrid[n - j - 1][i] = grid[i][j];
		}
	}
	DupGrid(tempGrid, grid);
}

bool GroupExist() {
	if (largestGroup.curB == EMPTY) return false;
	else return true;
}

void AutoPlay() {

	while (true) {
		FindLargestBlockGroup();
		if (!GroupExist()) return;
		
		Delete();
		
		Gravity();
		
		Rotate();

		Gravity();
	}
}

int main() {
	Init();

	AutoPlay();

	cout << score;

	return 0;
}

Before Optimization

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>

using namespace std;

const int MAX_N = 20;
const int BLACK = -1;
const int RAINBOW = 0;
const int EMPTY = -2;
// 상, 하, 좌, 우
const int ds[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

int n, m;
int grid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int tempGrid[MAX_N][MAX_N];
int score;

struct Group {
	int curB;
	// area, rainbowNum, i, j
	tuple<int, int, int, int> stat;

	Group(){}
	Group(int _curB, tuple<int, int, int, int> _stat) :
		curB(_curB), stat(_stat) { }
};

Group largestGroup, curGroup;

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

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

void InitVisited() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = false;
		}
	}
}

void InitTempGrid() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			tempGrid[i][j] = EMPTY;
		}
	}
}

bool InGrid(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < n;
}

void CurrentGroupBfs(int i, int j) {
	InitVisited();

	queue<pair<int, int>> q;
	int _curB = grid[i][j];
	int _area = 1;
	int _rainbowNum = 0;
	tuple<int, int> stdB = { i, j };

	q.push({ i, j });
	visited[i][j] = true;

	while (!q.empty()) {
		int ci, cj;
		tie(ci, cj) = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];
			if (!InGrid(ni, nj)) continue;
			if (visited[ni][nj]) continue;
			if (grid[ni][nj] == BLACK) continue;

			if (grid[ni][nj] == _curB) {
				q.push({ ni, nj });
				visited[ni][nj] = true;
				_area++;
				if (make_tuple(ni, nj) < stdB) stdB = make_tuple(ni, nj);
			}
			else if (grid[ni][nj] == RAINBOW) {
				q.push({ ni, nj });
				visited[ni][nj] = true;
				_area++;
				_rainbowNum++;
			}
		}
	}
	
	if (_area >= 2) {
		int stdi, stdj;
		tie(stdi, stdj) = stdB;
		curGroup = Group(_curB, make_tuple(_area, _rainbowNum, stdi, stdj));
		if (curGroup.stat > largestGroup.stat) {
			largestGroup = curGroup;
		}
	}
}

void FindLargestBlockGroup() {
	largestGroup = Group(EMPTY, make_tuple(0, 0, 0, 0));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] <= 0) continue;

			CurrentGroupBfs(i, j);
		}
	}
}

void Delete() {
	InitVisited();
	queue<pair<int, int>> q;
	int _a, _i, _j;
	tie(_a, ignore, _i, _j) = largestGroup.stat;

	// 1. get score
	score += _a * _a;

	// 2. get group place
	q.push({ _i, _j });
	visited[_i][_j] = true;

	while (!q.empty()) {
		int ci, cj;
		tie(ci, cj) = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];
			if (!InGrid(ni, nj)) continue;
			if (visited[ni][nj]) continue;

			if (grid[ni][nj] == largestGroup.curB || grid[ni][nj] == RAINBOW) {
				q.push({ ni, nj });
				visited[ni][nj] = true;
			}
		}
	}

	// 3. delete
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j]) grid[i][j] = EMPTY;
		}
	}
}

void Gravity() {
	int temp_col[MAX_N];
	for (int i = 0; i < n; i++) temp_col[i] = EMPTY;

	for (int j = 0; j < n; j++) {
		for (int i = 0; i < n; i++) temp_col[i] = EMPTY;
		int temp_i = n - 1;

		for (int i = n - 1; i >= 0; i--) {
			if (temp_i < 0) break;
			if (grid[i][j] == EMPTY) continue;
			if (grid[i][j] == BLACK) {
				temp_col[i] = BLACK;
				temp_i = i - 1;
			}
			if (grid[i][j] >= 0) {
				temp_col[temp_i] = grid[i][j];
				temp_i--;
			}
		}

		for (int i = 0; i < n; i++) {
			grid[i][j] = temp_col[i];
		}
	}
}

void DupGrid(int from[MAX_N][MAX_N], int to[MAX_N][MAX_N]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void Rotate() {
	InitTempGrid();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			tempGrid[n - j - 1][i] = grid[i][j];
		}
	}
	DupGrid(tempGrid, grid);
}

bool GroupExist() {
	if (largestGroup.curB == EMPTY) return false;
	else return true;
}

void AutoPlay() {

	while (true) {
		FindLargestBlockGroup();
		if (!GroupExist()) return;
		
		Delete();
		
		Gravity();
		
		Rotate();

		Gravity();
	}
}

int main() {
	Init();

	AutoPlay();

	cout << score;

	return 0;
}