백준 14499 (주사위 굴리기)

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

14499번: 주사위 굴리기

풀이

해당 문제 풀이의 핵심은 주사위의 회전 (동, 서, 북, 남 방향으로 회전) 을 구현하는 것과 회전하기전 주사위의 위치를 이동시켜 이동시킨 위치가 주어진 N * M 좌표 안에 존재하는지 체크하는 부분이다.

1. 주사위 회전구현

주사위의 각 면에 해당하는 크기 6개의 배열이 필요하며, 이동했을때 각 면이 어떻게 이동했는지 알수있는 check 배열이 하나 필요하다.

위와 같이 각 방향을 인덱스로 관리하며 위 = 0, 오른쪽 = 1 ..... 이와 같이 관리하며 동쪽으로 회전시 각 인덱스에 어떠한 값이 들어가는지 생각해주어야 한다.

위와 좌표는 동, 서, 북, 남 방향으로 회전 시킨 뒤 각 인덱스에 몇번 인덱스의 값이 들어가는 지를 나타내주는 배열이다.

EX ) 동쪽으로 회전시 주사위의 0번째 인덱스에는 기존 인덱스의 dice의 배열에 0번째 인덱스에 해당하는값 즉

dic[0] = dic[dice[0][0]] 에 해당하는 값을 넣어주면 결과적으로 동쪽으로 회전시킨 뒤 주사위의 위에 있는 값은 이전 주사위의 2번 idx 즉 이전 주사위의 왼쪽 면에 해당하는 값이 위로 오게된다. 이와 같은 방식으로 주사위의 회전을 구현하면 된다.

마지막으로 각 명령어의 횟수만큼 재귀하며 각 명령어에 해당하는 회전을 수행하고 주사위의 위에 면에 해당하는 값을 출력하면 된다.

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <queue>

using namespace std;
// 맵에서 이동의 위한 배열
int check[4][2] = {
	0, 1,
	0, -1,
	-1, 0,
	1, 0,
};
int mvCnt;
int my, mx;
int map[20][20];
int cmdList[1001];

// 동서북남 순서대로 회전할때 변경되는 인덱스의 값
int dice[4][6] = {
	{ 2, 0, 5, 3, 4, 1 },
	{ 1, 5, 0, 3, 4, 2 }, 
	{ 4, 1, 2, 0, 5, 3 },
	{ 3, 1, 2, 5, 0, 4 },
};

int dic[6];

void spin(int y, int x, int cmd){
	// 바닥 : idx 5
	// 위 : idx 0

	int cpDice[6];
	for (int i = 0; i < 6; ++i){
		cpDice[i] = dic[dice[cmd][i]];
	}
	memcpy(dic, cpDice, 4 * 6);
}

void dfs(int level, int y, int x){
	if (level == mvCnt){
		return;
	}
	int cmd = cmdList[level] -1;
	int dy = y + check[cmd][0];
	int dx = x + check[cmd][1];

	// 이동한 좌표가 map안에 존재할때만 주사위를 회전 및 출력
	if (dy >= 0 && dx >= 0 && dy < my && dx < mx){
		spin(y, x, cmd);
		if (map[dy][dx] == 0){
			map[dy][dx] = dic[5];
		}
		else{
			dic[5] = map[dy][dx];
			map[dy][dx] = 0;
		}
		printf("%d\n", dic[0]);
		dfs(level + 1, dy, dx);
	}
    
    // 만약 좌표를 벗어날경우 현재 y x 좌표와 다음 명령어순서로 진행
	else{
		dfs(level + 1, y, x);
	}

}


int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);
	int sy, sx;
	cin >> my >> mx >> sy >> sx >> mvCnt;
	for (int i = 0; i < my; ++i){
		for (int j = 0; j < mx; ++j){
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < mvCnt; ++i){
		cin >> cmdList[i];
	}
	dfs(0, sy, sx);


}