백준 23288번 : 주사위 굴리기2

sol : 38' 28''

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

Learnings

• 전처리를 하면 좋은 문제였다.
• 실전에서도 이렇게 전처리 생각이 먼저 떠오르려나.
  • 미지의 영역 탈출도 같은 논리였다.
• 전처리를 하고 수행하니까 8ms에서 0ms로 줄었다.

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

using namespace std;
// 1-based
#define MAX_N 21
#define MAX_M 21

#define EAST 0
#define SOUTH 1
#define WEST 2
#define NORTH 3

int n, m, k;
int score;
int scoreBoard[MAX_N][MAX_M];
bool visited[MAX_N][MAX_M];
int preprocessedBoard[MAX_N][MAX_M];

struct Dice {
	int r;
	int c;
	int dir;
	int top;
	int front;
	int right;

	Dice() :
		r(1), c(1), dir(EAST), top(1), front(5), right(3) {
	}
};
Dice dice;

// 동, 남, 서, 북
const int ds[4][2] = {
	{0,1},
	{1,0},
	{0,-1},
	{-1,0}
};

void Init() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> scoreBoard[i][j];
		}
	}
}

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

void ScoreBFS(int i, int j) {
	int curNum = scoreBoard[i][j];
	queue<pair<int, int>> q;
	vector<pair<int, int>> curArea;

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

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

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

			if (!InGrid(ni, nj) || visited[ni][nj] || scoreBoard[ni][nj] != curNum) continue;

			visited[ni][nj] = true;
			q.push({ ni, nj });
			curArea.push_back({ ni, nj });
		}
	}

	for (int i = 0; i < curArea.size(); i++) {
		preprocessedBoard[curArea[i].first][curArea[i].second] = curNum * curArea.size();
	}
}

void ScoreBoardPreprocess() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (visited[i][j]) continue;
			ScoreBFS(i, j);
		}
	}
}

void Translator(int dir) {
	int ct = dice.top, cf = dice.front, cr = dice.right;
	if (dir == EAST) {
		dice.top = 7 - cr;
		dice.right = ct;
	}
	else if (dir == WEST) {
		dice.top = cr;
		dice.right = 7 - ct;
	}
	else if (dir == SOUTH) {
		dice.front = ct;
		dice.top = 7 - cf;
	}
	else if (dir == NORTH) {
		dice.front = 7 - ct;
		dice.top = cf;
	}
}

void Roll() {
	int cd = dice.dir;
	int ni = dice.r + ds[cd][0], nj = dice.c + ds[cd][1];
	if (!InGrid(ni, nj)) {
		cd = (cd + 2) % 4;
		ni = dice.r + ds[cd][0], nj = dice.c + ds[cd][1];

	}

	dice.r = ni, dice.c = nj, dice.dir = cd;
	Translator(cd);
}

void NextDir() {
	int A = 7 - dice.top, B = scoreBoard[dice.r][dice.c];
	if (A > B) dice.dir = (dice.dir + 1 == 4) ? 0 : dice.dir + 1;
	else if (A < B) dice.dir = (dice.dir - 1 == -1) ? 3 : dice.dir - 1;
}

int main() {
	Init();

	ScoreBoardPreprocess();

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

		score += preprocessedBoard[dice.r][dice.c];

		NextDir();
	}

	cout << score;

	return 0;
}