고대 문명 유적 탐사

Simulation, BFS

• 평균 : 180'

---

sol : 174' 13''

• 수행 시간 : 9ms
• 메모리 : 0MB

Learnings

• 구현 자체는 이제 다 할 수 있으니까, 보다 간단한 방법을 생각해보자.
• 처음에 설계할 때부터 천천히 고민해보자.
• 삭제 대상이 연결 성분이면 bool 배열보다 좌표 벡터가 더 적합할 때가 많다.
• 상태는 가능하면 배열 값 자체로 표현하라.
• 평가용 로직과 실제 반영 로직을 가능하면 분리하라. 지금은 TEST / REAL로 처리했지만, 더 좋은 설계에서는 보드 자체를 분리한다.
• 회전은 90도 하나만 검증하고 반복 적용하는 방향이 안전하다.

---

리펙토링 버전

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

#define MAX_GRID 6
#define TRAVEL_GRID 3
#define TEST 1
#define REAL 0
#define DIRECTIONS 4
#define EMPTY 0

using namespace std;

int k, m;
int grid[MAX_GRID][MAX_GRID];
// 회전 결과 임시 저장 그리드
int tempGrid[MAX_GRID][MAX_GRID];
// 각 턴 마다 획득한 유물의 가치의 총합
int totalScore;
// 하, 상, 우, 좌
int ds[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
// 추가 유물 인덱스 현황 저장
int next_id = 1;


vector<int> treasure;
bool visited[MAX_GRID][MAX_GRID];

/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////


void Debug(int g[MAX_GRID][MAX_GRID]) {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i < MAX_GRID; i++) {
		for (int j = 1; j < MAX_GRID; j++) {
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void InitVisited(bool v[MAX_GRID][MAX_GRID]) {
	for (int i = 1; i < MAX_GRID; i++) {
		for (int j = 1; j < MAX_GRID; j++) {
			v[i][j] = false;
		}
	}
}

void DuplicateGrid(int from[MAX_GRID][MAX_GRID], int to[MAX_GRID][MAX_GRID]) {
	for (int i = 1; i < MAX_GRID; i++) {
		for (int j = 1; j < MAX_GRID; j++) {
			to[i][j] = from[i][j];
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i < MAX_GRID && 1 <= j && j < MAX_GRID;
}

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

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

	treasure.resize(m + 1);

	for (int i = 1; i <= m; i++) {
		cin >> treasure[i];
	}
}

// ri, rj 기준 3x3 그리드 시계 방향으로 degree만큼 회전한 temp grid 제공
void Rotate(int ri, int rj, int degree) {
	int rotateTempGrid[MAX_GRID][MAX_GRID];

	DuplicateGrid(grid, tempGrid);
	DuplicateGrid(tempGrid, rotateTempGrid);
	for (int r = 0; r <= degree; r++) {
		for (int i = 1; i <= TRAVEL_GRID; i++) {
			for (int j = 1; j <= TRAVEL_GRID; j++) {
				rotateTempGrid[j + (ri - 1)][TRAVEL_GRID - i + 1 + (rj - 1)] = tempGrid[ri + i - 1][rj + j - 1];
			}
		}
		DuplicateGrid(rotateTempGrid, tempGrid);
	}
}

void Fill() {
	for (int j = 1; j < MAX_GRID; j++) {
		for (int i = MAX_GRID - 1; i > 0; i--) {
			if (grid[i][j] == EMPTY) {
				grid[i][j] = treasure[next_id++];
			}
		}
	}
}

int CalScoreByBfs(int i, int j, int g[MAX_GRID][MAX_GRID], bool isTest) {
	queue<pair<int, int>> q;
	q.push({ i, j });
	int treasureNum = g[i][j];
	vector<pair<int, int>> deleteCell;
	deleteCell.push_back({ i, j });

	while (!q.empty()) {
		int ci = q.front().first;
		int cj = q.front().second;
		q.pop();

		for (int d = 0; d < DIRECTIONS; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (InGrid(ni, nj) && !visited[ni][nj] && g[ni][nj] == treasureNum) {
				visited[ni][nj] = true;
				deleteCell.push_back({ ni, nj });
				q.push({ ni, nj });
			}
		}
	}

	// 3개 이상 연결된 경우에만 점수 취급
	if (deleteCell.size() >= 3) {
		if (!isTest) {
			// 칸 삭제
			for (int i = 0; i < deleteCell.size(); i++) {
				grid[deleteCell[i].first][deleteCell[i].second] = 0;
			}
		}
		return deleteCell.size();
	}
	else return 0;
}

int GainCalculator(bool isTest) {
	int score = 0;

	InitVisited(visited);

	if (isTest) {
		for (int i = 1; i < MAX_GRID; i++) {
			for (int j = 1; j < MAX_GRID; j++) {
				if (!visited[i][j]) {
					visited[i][j] = true;
					score += CalScoreByBfs(i, j, tempGrid, isTest);
				}
			}
		}
	}
	else {
		for (int i = 1; i < MAX_GRID; i++) {
			for (int j = 1; j < MAX_GRID; j++) {
				if (!visited[i][j]) {
					visited[i][j] = true;
					score += CalScoreByBfs(i, j, grid, isTest);
				}
			}
		}
	}

	return score;
}

tuple<int, int, int> FindMaxInitGain() {
	int maxScore = INT_MIN;
	tuple<int, int, int> maxRotationInfo = { -1, -1 ,-1 };

	// 회전 각도가 가장 작은 것
	for (int deg = 0; deg <= 2; deg++) {
		// 회전 중심 각도의 열이 가장 작은 것
		for (int j = 2; j <= 4; j++) {
			// 회전 중심 각도의 행이 가장 작은 것
			for (int i = 2; i <= 4; i++) {
				Rotate(i - 1, j - 1, deg);
				int curScore = GainCalculator(TEST);
				if (curScore > maxScore) {
					maxScore = curScore;
					maxRotationInfo = { i - 1, j - 1, deg };
				}
			}
		}
	}

	return maxRotationInfo;
}

void InitialGain() {
	// 1. 유물 1차 획득 가치를 최대화 하는 방법 찾기
	// 90도, 180도, 270도, 선택된 격자는 무조건 회전해야 함
	int max_i, max_j, max_d;
	tie(max_i, max_j, max_d) = FindMaxInitGain();

	// 2. 유물 1차 획득 가치 최대화 방법으로 격자 회전 
	Rotate(max_i, max_j, max_d);
	DuplicateGrid(tempGrid, grid);

	// 3. 1차 가치 계산
	totalScore += GainCalculator(REAL);
	Fill();
}

void ChainGain() {
	while (true) {
		int curScore = GainCalculator(REAL);
		totalScore += curScore;
		if (curScore > 0) {
			Fill();
		}
		else break;
	}
}

int main() {
	Init();

	for (int turn = 1; turn <= k; turn++) {
		totalScore = 0;

		// 1. 유물 1차 획득
		InitialGain();

		// 2. 연쇄 획득
		ChainGain();

		// 만약 점수를 얻지 못했다면 즉시 종료
		if (totalScore == 0) break;

		cout << totalScore << ' ';
	}

	return 0;
}

초기 버전

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

#define MAX_GRID 6
#define TRAVEL_GRID 3
#define TEST 1
#define REAL 0
#define DIRECTIONS 4

// 90도 회전
#define ONE_FOUR 0
// 180도 회전
#define TWO_FOUR 1
// 270도 회전
#define THREE_FOUR 2

using namespace std;

int k, m;
int grid[MAX_GRID][MAX_GRID];
// 회전 결과 임시 저장 그리드
int tempGrid[MAX_GRID][MAX_GRID];
// 각 턴 마다 획득한 유물의 가치의 총합
int totalScore;
// 하, 상, 우, 좌
int ds[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
// 추가 유물 인덱스 현황 저장
int next_id = 1;


vector<int> treasure;
bool visited[MAX_GRID][MAX_GRID];
bool deleteVisited[MAX_GRID][MAX_GRID];

/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////


void Debug(int g[MAX_GRID][MAX_GRID]) {
	cout << endl << "DEBUG" << endl;
	for (int i = 1; i < MAX_GRID; i++) {
		for (int j = 1; j < MAX_GRID; j++) {
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void InitVisited(bool v[MAX_GRID][MAX_GRID]) {
	for (int i = 1; i < MAX_GRID; i++) {
		for (int j = 1; j < MAX_GRID; j++) {
			v[i][j] = false;
		}
	}
}

void DuplicateGrid(int from[MAX_GRID][MAX_GRID], int to[MAX_GRID][MAX_GRID]) {
	for (int i = 1; i < MAX_GRID; i++) {
		for (int j = 1; j < MAX_GRID; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void UpdateDeletedVisit(bool from[MAX_GRID][MAX_GRID], bool to[MAX_GRID][MAX_GRID]) {
	for (int i = 1; i < MAX_GRID; i++) {
		for (int j = 1; j < MAX_GRID; j++) {
			if (from[i][j] == true) to[i][j] = true;
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= MAX_GRID && 1 <= j && j <= MAX_GRID;
}

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

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

	treasure.resize(m + 1);

	for (int i = 1; i <= m; i++) {
		cin >> treasure[i];
	}
}

// ri, rj 기준 3x3 그리드 시계 방향으로 degree만큼 회전한 temp grid 제공
void Rotate(int ri, int rj, int degree) {
	// temp grid를 grid로 초기화
	DuplicateGrid(grid, tempGrid);

	// 90도 회전
	if (degree == ONE_FOUR) {
		for (int i = 1; i <= TRAVEL_GRID; i++) {
			for (int j = 1; j <= TRAVEL_GRID; j++) {
				tempGrid[j + (ri - 1)][TRAVEL_GRID - i + 1 + (rj - 1)] = grid[ri + i - 1][rj + j - 1];
			}
		}
	}

	// 180도 회전
	else if (degree == TWO_FOUR) {
		int tempGrid2[MAX_GRID][MAX_GRID];
		// x축 반전 후
		for (int j = 1; j <= TRAVEL_GRID; j++) {
			for (int i = 1; i <= TRAVEL_GRID; i++) {
				tempGrid[TRAVEL_GRID - i + 1 + (ri - 1)][j + (rj - 1)] = grid[ri + i - 1][rj + j - 1];
			}
		}
		DuplicateGrid(tempGrid, tempGrid2);

		// y축 반전
		for (int i = 1; i <= TRAVEL_GRID; i++) {
			for (int j = 1; j <= TRAVEL_GRID; j++) {
				tempGrid[i + (ri - 1)][TRAVEL_GRID - j + 1 + (rj - 1)] = tempGrid2[ri + i - 1][rj + j - 1];
			}
		}
	}

	// 270도 회전
	else if (degree == THREE_FOUR) {
		// 반시계 방향 90도 회전
		for (int i = 1; i <= TRAVEL_GRID; i++) {
			for (int j = 1; j <= TRAVEL_GRID; j++) {
				tempGrid[TRAVEL_GRID - j + 1 + (ri - 1)][i + (rj - 1)] = grid[ri + i - 1][rj + j - 1];
			}
		}
	}
}

void DeleteAndFill(bool v[MAX_GRID][MAX_GRID]) {
	for (int j = 1; j < MAX_GRID; j++) {
		for (int i = MAX_GRID - 1; i > 0; i--) {
			if (v[i][j]) {
				grid[i][j] = treasure[next_id++];
			}
		}
	}
}

int CalScoreByBfs(int i, int j, int g[MAX_GRID][MAX_GRID], bool isTest) {
	queue<pair<int, int>> q;
	q.push({ i, j });
	int treasureNum = g[i][j];
	int count = 1;

	// 이번 턴에 방문한 칸들을 따로 저장하기 위한 용도
	bool tempVisited[MAX_GRID][MAX_GRID];
	InitVisited(tempVisited);
	tempVisited[i][j] = true;

	while (!q.empty()) {
		int ci = q.front().first;
		int cj = q.front().second;
		q.pop();

		for (int d = 0; d < DIRECTIONS; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (InGrid(ni, nj) && !visited[ni][nj] && !tempVisited[ni][nj] && g[ni][nj] == treasureNum) {
				count++;
				visited[ni][nj] = true;
				tempVisited[ni][nj] = true;
				q.push({ ni, nj });
			}
		}
	}

	// 3개 이상 연결된 경우에만 점수 취급
	if (count >= 3) {
		if (!isTest) {
			// 칸 삭제
			UpdateDeletedVisit(tempVisited, deleteVisited);
		}
		return count;
	}
	else return 0;
}

int GainCalculator(bool isTest) {
	int score = 0;

	InitVisited(visited);

	if (isTest) {
		for (int i = 1; i < MAX_GRID; i++) {
			for (int j = 1; j < MAX_GRID; j++) {
				if (!visited[i][j]) {
					visited[i][j] = true;
					score += CalScoreByBfs(i, j, tempGrid, isTest);
				}
			}
		}
	}
	else {
		InitVisited(deleteVisited);

		for (int i = 1; i < MAX_GRID; i++) {
			for (int j = 1; j < MAX_GRID; j++) {
				if (!visited[i][j]) {
					visited[i][j] = true;
					score += CalScoreByBfs(i, j, grid, isTest);
				}
			}
		}

		DeleteAndFill(deleteVisited);
	}

	return score;
}

tuple<int, int, int> FindMaxInitGain() {
	int si, sj, degree;
	int maxScore = INT_MIN;
	tuple<int, int, int> maxRotationInfo = { -1, -1 ,-1 };

	// 회전 각도가 가장 작은 것
	for (int deg = 0; deg <= 2; deg++) {
		// 회전 중심 각도의 열이 가장 작은 것
		for (int j = 2; j <= 4; j++) {
			// 회전 중심 각도의 행이 가장 작은 것
			for (int i = 2; i <= 4; i++) {
				Rotate(i - 1, j - 1, deg);
				int curScore = GainCalculator(TEST);
				if (curScore > maxScore) {
					maxScore = curScore;
					maxRotationInfo = { i - 1, j - 1, deg };
				}
			}
		}
	}

	return maxRotationInfo;
}

void InitialGain() {
	// 1. 유물 1차 획득 가치를 최대화 하는 방법 찾기
	// 90도, 180도, 270도, 선택된 격자는 무조건 회전해야 함
	int max_i, max_j, max_d;
	tie(max_i, max_j, max_d) = FindMaxInitGain();

	// 2. 유물 1차 획득 가치 최대화 방법으로 격자 회전 
	Rotate(max_i, max_j, max_d);
	DuplicateGrid(tempGrid, grid);

	// 3. 1차 가치 계산
	totalScore += GainCalculator(REAL);
}

void ChainGain() {
	int curScore = GainCalculator(REAL);

	while (curScore > 0) {
		totalScore += curScore;
		curScore = GainCalculator(REAL);
	}
}

int main() {
	Init();

	for (int turn = 1; turn <= k; turn++) {
		totalScore = 0;

		// 1. 유물 1차 획득
		InitialGain();

		// 2. 연쇄 획득
		ChainGain();

		// 만약 점수를 얻지 못했다면 즉시 종료
		if (totalScore == 0) break;

		cout << totalScore << ' ';
	}

	return 0;
}