백준 - 주사위 굴리기 2 (23288번)

백준 - 주사위 굴리기 2 (23288번)

다행히 시험장에서 풀때랑 비슷한 느낌으로 풀었다.

근데 집에서 푸니까 10분만에 푼다; 시험장에선 1시간 걸렸는데...
다시 풀어서 그런건지;

엄청 복잡한 구현은 없고, 주어진데로 구현하면 된다.

주사위는 dice[3]으로 관리해서 윗면, 앞면, 옆면 순서대로 관리하면서 굴릴때마다 업데이트 해주고, map과 붙어있는 값을 반환해준다.

해당 코드는 8ms 나왔는데, 0ms 나온 코드를 보니까 bfs부분만 더 최적화해준 것 같다.

난 그냥 map[i][j] 만날때마다 bfs를 돌리는데, 이를 최적화 하려면 dice를 굴리기 전부터 미리 map에 대해서 bfs를 다 구해놓으면 된다.

그리고 visitMap을 따로 global하게 관리해서 이미 방문한 map[i][j]에 대해서는 bfs를 다시 돌지 않고, 미리 contiguous area 값을 다 기록해놓는다.
난 이렇게까진 안했다. 수정은 금방할 수 있을 것 같다.

#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

int n, m, k;
int map[21][21];

int rowDir[4] = { 0, 1, 0, -1 };
int colDir[4] = { 1, 0, -1, 0 };
int dice[3] = { 1, 5, 3 };

typedef struct __pos {
	int row;
	int col;
}pos;

int get_calculate_area(int row, int col)
{
	queue<pos> q;
	int num = map[row][col];
	int visit[21][21] = { 0, };

	visit[row][col] = 1;
	q.push({ row, col });
	int cnt = 1;
	while (1) {
		if (q.empty())
			break;
		pos cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			pos entity;
			entity.row = cur.row + rowDir[i];
			entity.col = cur.col + colDir[i];
			if (entity.row < 0 || entity.row >= n)
				continue;
			if (entity.col < 0 || entity.col >= m)
				continue;
			if (map[entity.row][entity.col] != num)
				continue;
			if (visit[entity.row][entity.col] == 1)
				continue;
			//printf("[%d][%d]\n", num, cnt, num * cnt);

			visit[entity.row][entity.col] = 1;
			q.push(entity);
			cnt++;
		}
	}
	return num * cnt;
}
int move_dice_and_get_bottom(int dir)
{
	int bottom = -1;
	// 0 : 우측으로 굴림
	// 1 : 앞으로 굴림
	// 2 : 왼쪽으로 굴림
	// 3 : 위쪽으로 굴림
	if (dir == 0) {
		bottom = dice[2];
		dice[2] = dice[0];
		dice[0] = 7 - bottom;
	}
	else if (dir == 1) {
		bottom = dice[1];
		dice[1] = dice[0];
		dice[0] = 7 - bottom;
	}
	else if (dir == 2) {
		bottom = 7 - dice[2];
		dice[2] = 7 - dice[0];
		dice[0] = 7 - bottom;
	}
	else if (dir == 3) {
		bottom = 7 - dice[1];
		dice[1] = 7 - dice[0];
		dice[0] = 7 - bottom;
	}
	return bottom;
}
int main(void)
{
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			cin >> map[i][j];
		
	int dir = 0;
	int row = 0, col = 0;
	int nrow = row, ncol = col;
	// 동 : 0, 남 : 1, 서 : 2, 북 : 3
	int result = 0;
	for (int i = 0; i < k; i++) {
		row = nrow + rowDir[dir];
		col = ncol + colDir[dir];
		if (row < 0 || row > n - 1 || col < 0 || col > m - 1) {
			dir = (dir + 2) % 4;
			row = nrow + rowDir[dir];
			col = ncol + colDir[dir];
		}
		nrow = row;
		ncol = col;

		int bottom = move_dice_and_get_bottom(dir);

		if (bottom > map[row][col])
			dir = (dir + 1) % 4;
		else if (bottom < map[row][col])
			dir = (dir + 3) % 4;
		
		result += get_calculate_area(row, col);
	}
	cout << result << "\n";
	return 0;
}