[PS] 백준 23288번 주사위 굴리기 2

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

문제 설명

각 칸에 10미만의 자연수가 있는 2차원 배열(지도)가 주어진다. (1, 1)위치에서 주사위(1~6)를 동쪽방향으로 굴리는 것을 시작으로해서, 다음칸의 숫자와 주사위 바닥면의 숫자를 비교해서 주어진 조건대로 방향을 바꾸거나 바꾸지 않거나 하면 된다. 또한 칸에 도착했을 때, 점수를 얻을 수 있는데, 어느 칸에 도착했을 때 얻을 수 있는 점수는 "그 칸에 쓰여진 숫자와 동일한 숫자이면서, 그 칸과 인접해서 이어지는 칸들의 수 * 숫자" 이다.

1. 각 칸에 도착했을 때 얻을 수 있는 점수를 구할 때는 그래프 탐색을 사용하면 된다. DFS 혹은 BFS. 미리 계산해서 score[][] 에 메모해 놓는다. 그 다음, 시뮬레이션을 시작하면 된다. dy, dx 를 이용하여 주사위를 굴리면 되고, 방향 전환도 dy dx를 시계/반시계 방향으로 정의해놓았다면 간단하다. 다만 주사위 바닥면을 알고있어야 하므로 주사위를 굴릴 때마다 주사위 전개도를 갱신해 주어야 하는데 이게 이 문제의 포인트가 아닌가 싶다. 처음에는 diceVertical, diceHorizontal 라는 이름의 Deque을 두 개 두고, 총 8개의 주사위 눈 수를 저장하는 주사위 전개도를 구현했는데, 구현하다보니 주사위 바닥면만 공유되는게 아니라 윗 면도 공유가 되고있어서 차라리 2차원 배열로 구현하는 것이 훨씬 나았다. 무엇보다 처음 주사위 굴리는 재귀를 시작할 때 먼저 굴리고 시작하는지 어디서부터 시작하는지가 헷갈린 것 때문에 삽질을 많이 했다,,,

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

using namespace std;

int n, m, k, ans;
int grid[20][20], score[20][20];
bool visited[20][20];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
int dice[4][3] = { { 0, 2, 0}, {4, 1, 3}, {0, 5, 0}, {0, 6, 0} };

bool inRange(int row, int col) {
	return 0 <= row && row < n && 0 <= col && col < m;
}

int dfs(int row, int col, int num, queue<pair<int, int>> &q) {
	int cnt = 1;
	for (int i = 0; i < 4; i++) {
		int nRow = row + dy[i];
		int nCol = col + dx[i];

		if (inRange(nRow, nCol) && grid[nRow][nCol] == num && visited[nRow][nCol] == false) {
			visited[nRow][nCol] = true;
			q.push({ nRow, nCol });
			cnt += dfs(nRow, nCol, num, q);
		}
	}

	return cnt;
}

void calScoreGrid() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j]) {
				queue<pair<int, int>> q;
				visited[i][j] = true;
				int num = grid[i][j];
				int curScore = dfs(i, j, num, q) * num;
				score[i][j] = curScore;
				while (!q.empty()) {
					int row, col;
					tie(row, col) = q.front();
					q.pop();
					score[row][col] = curScore;
				}
			}
		}
	}
}

void rollDice(int dir) {
	if (dir == 0) {
		int tmp = dice[1][0];
		dice[1][0] = dice[3][1];
		dice[3][1] = dice[1][2];
		dice[1][2] = dice[1][1];
		dice[1][1] = tmp;
	}
	else if (dir == 1) {
		int tmp = dice[3][1];
		dice[3][1] = dice[2][1];
		dice[2][1] = dice[1][1];
		dice[1][1] = dice[0][1];
		dice[0][1] = tmp;
	}
	else if (dir == 2) {
		int tmp = dice[1][0];
		dice[1][0] = dice[1][1];
		dice[1][1] = dice[1][2];
		dice[1][2] = dice[3][1];
		dice[3][1] = tmp;
	}
	else if (dir == 3) {
		int tmp = dice[0][1];
		dice[0][1] = dice[1][1];
		dice[1][1] = dice[2][1];
		dice[2][1] = dice[3][1];
		dice[3][1] = tmp;
	}
}

void go(int row, int col, int moveCnt, int curDir) {
	if (moveCnt == k) {
		return;
	}

	ans += score[row][col];

	int bottom = dice[3][1];
	int gridNum = grid[row][col];
	if (bottom > gridNum) {
		curDir = (curDir + 1) % 4;
	}
	else if (bottom < gridNum) {
		curDir = (curDir + 4 - 1) % 4;
	}

	int nRow = row + dy[curDir];
	int nCol = col + dx[curDir];

	if (!inRange(nRow, nCol)) {
		curDir = (curDir + 2) % 4;
		nRow = row + dy[curDir];
		nCol = col + dx[curDir];
	}

	// 주사위를 curDir 방향으로 굴린다 전개도와 위치가 변함
	rollDice(curDir);
	go(nRow, nCol, moveCnt + 1, curDir);
}

int main() {
	cin >> n >> m >> k;

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

	calScoreGrid();

	rollDice(0);
	go(0, 1, 0, 0);

	cout << ans;
}