정육면체 한번 더 굴리기

Simulation, BFS

평균 : 180'

---

sol : 65' 54''

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

Learnings

• 전처리가 가능해보이면 먼저 전처리해놓고 접근해도 좋을 것 같은데, 어차피 삼성 1번 문제 특성상 시간이나 메모리 성능을 강제하는 문제는 아니므로, 만약 시간이 남아서 최적화할 시간이 남았다면 한번 고려해보자.

#include <iostream>
#include <queue>

#define MAX_N 21
#define RIGHT 0
#define DOWN 1
#define LEFT 2
#define UP 3
#define TOP 4
#define BOTTOM 5

// 회전 방향
#define CW 0
#define CCW 1

using namespace std;

int n, m;
int grid[MAX_N][MAX_N];
// 우, 하, 좌, 상
int ds[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
bool visited[MAX_N][MAX_N];

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

	Dice() {}
	Dice(int _r, int _c, int _dir, int _right, int _down, int _top) :
		r(_r), c(_c), dir(_dir), right(_right), down(_down), top(_top) {
	}
};

Dice dice;

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

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

	dice = Dice(1, 1, RIGHT, 3, 2, 1);
}

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

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

void GridMove() {
	int ni = dice.r + ds[dice.dir][0], nj = dice.c + ds[dice.dir][1], nd = dice.dir;

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

	dice.r = ni, dice.c = nj, dice.dir = nd;
}

void DiceRoll() {
	int temp_top = dice.top, temp_down = dice.down, temp_right = dice.right;
	if (dice.dir == RIGHT) {
		dice.top = 7 - temp_right;
		dice.right = temp_top;
	}
	else if (dice.dir == DOWN) {
		dice.top = 7 - temp_down;
		dice.down = temp_top;
	}
	else if (dice.dir == LEFT) {
		dice.top = temp_right;
		dice.right = 7 - temp_top;
	}
	else if (dice.dir == UP) {
		dice.top = temp_down;
		dice.down = 7 - temp_top;
	}
}

void Rotate(int wise) {
	if (wise == CW) {
		dice.dir = (dice.dir + 1) % 4;
	}
	else if (wise == CCW) {
		dice.dir = (dice.dir + 3) % 4;
	}
}

void DiceMoveAndRoll() {
	// 1. get next cell in grid
	GridMove();

	// 2. dice roll in dice itself
	DiceRoll();
}

void NextDirection() {
	int diceBottom = 7 - dice.top;
	if (diceBottom > grid[dice.r][dice.c]) Rotate(CW);
	else if (diceBottom < grid[dice.r][dice.c]) Rotate(CCW);
}

int GetScore() {
	InitVisited();
	int curNum = grid[dice.r][dice.c];
	int cnt = 1;

	queue<pair<int, int>> q;
	q.push({ dice.r, dice.c });
	visited[dice.r][dice.c] = 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] && grid[ni][nj] == curNum) {
				visited[ni][nj] = true;
				q.push({ ni, nj });
				cnt++;
			}
		}
	}

	return cnt * curNum;
}

int main() {
	int score = 0;

	Init();

	for (int turn = 1; turn <= m; turn++) {
		// 1. dice move roll
		DiceMoveAndRoll();

		// 2. get score
		score += GetScore();

		// 3. find next direction
		NextDirection();
	}

	cout << score;

	return 0;
}