[백준] 14499번 주사위 굴리기

문제

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

풀이

처음에는 주사위를 굴릴 때 윗면과 바닥면만 바뀌는걸로 생각하고 시작했다.

문제에서 전개도를 준 점을 생각해보니 이동할 때마다 주사위의 상태를 바꿔줘야했다.

주사위를 정육면체라고 생각하고 cube[6] 을 만들어 각 면의 정보를 저장했다.

이동할 때 상태변화는 다음과 같다.

# 동쪽으로 이동하는 경우

1. 이전 칸에서의 오른쪽 면이 현재 칸에서의 바닥면이 된다.
2. 이전 칸에서의 왼쪽 면이 현재 칸에서의 윗면이 된다.
3. 이전 칸에서의 바닥면이 현재 칸에서의 왼쪽 면이 된다.
4. 이전 칸에서의 윗면이 현재 칸에서의 오른쪽 면이 된다.

# 서쪽으로 이동하는 경우

1. 오른쪽 -> 윗면
2. 왼쪽 -> 바닥
3. 윗면 -> 왼쪽
4. 바닥 -> 오른쪽

# 북쪽으로 이동하는 경우

1. 앞쪽 -> 윗면
2. 뒤쪽 -> 바닥면
3. 윗면 -> 뒤쪽
4. 바닥 -> 앞쪽

# 남쪽으로 이동하는 경우

1. 뒤쪽 -> 윗면
2. 앞쪽 -> 바닥면
3. 바닥 -> 뒤쪽
4. 윗면 -> 앞쪽

Dfs를 통해 현재 주사위가 위치한 칸부터 이동 명령에 따라 다음 칸의 좌표를 정해줬다.

이동하기 전에 다음 칸이 0인지 아닌지에 따라 변환을 해주고 다음 칸으로 넘어갔다.

소스코드

#include <iostream>
#include <vector>

using namespace std;

#define MAX_SIZE 21
#define MAX_K 1001

int n, m;
int a[MAX_SIZE][MAX_SIZE];
vector<int> command;
int k;
// left, right, back, front, top, bottom
int cube[6]; // 주사위 상태 저장
// 동(1), 서(2), 북(3), 남(4)
int dx[5] = { 0,0,0,-1,1 };
int dy[5] = { 0,1,-1,0,0 };

// 명령에 따라서 주사위 상태를 바꿔주는 함수
void ChangeCubeState(int curr_command)
{
    int left = cube[0], right = cube[1];
    int back = cube[2], front = cube[3];
    int top = cube[4], bottom = cube[5];

    // 동쪽 이동
    if (curr_command == 1)
    {
        // left = bottom, right = top
        cube[0] = bottom;
        cube[1] = top;
        // bottom = right, top = left
        cube[4] = left;
        cube[5] = right;
    }
    // 서쪽 이동
    else if (curr_command == 2)
    {
        // left = top, right = bottom
        cube[0] = top;
        cube[1] = bottom;
        // bottom = left, top = right
        cube[4] = right;
        cube[5] = left;
    }
    // 북쪽 이동
    else if (curr_command == 3)
    {
        // back = top , front = bottom
        cube[2] = top;
        cube[3] = bottom;
        // top = front, bottom = back
        cube[4] = front;
        cube[5] = back;
    }
    // 남쪽 이동
    else if (curr_command == 4)
    {
        // back = top, front = bottom
        cube[2] = bottom;
        cube[3] = top;
        // top = back, bottom = front
        cube[4] = back;
        cube[5] = front;
    }
}

void Dfs(int x, int y, int command_index, bool print)
{
    if (print)
        cout << cube[4] << "\n";

    if (command_index == k) return;

    int curr_command = command[command_index];

    // 다음 칸의 좌표
    int next_x = x + dx[curr_command], next_y = y + dy[curr_command];

    // 지도 밖이면 다음 명령을 실행하고 출력하지 않는다.
    if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m)
    {
        Dfs(x, y, command_index + 1,false);
        return;
    }

    // 다음 칸이 0이면 다음 칸을 바닥면에 적힌 숫자로 복사
    if (a[next_x][next_y] == 0)
    {
        ChangeCubeState(curr_command);
        a[next_x][next_y] = cube[5];
        Dfs(next_x, next_y, command_index + 1,true);
    }
    // 0이 아닌 경우에는 칸에 써있는 수를 바닥면으로 복사해주고 칸에 써있는 수는 0으로 만든다.
    else
    {
        ChangeCubeState(curr_command);
        cube[5] = a[next_x][next_y];
        a[next_x][next_y] = 0;
        Dfs(next_x, next_y, command_index + 1,true);
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int x, y;

    cin >> n >> m >> x >> y >> k;

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

    // 이동명령 저장
    for (int i = 0; i < k; i++)
    {
        int com;
        cin >> com;
        command.push_back(com);
    }

    Dfs(x, y, 0,false);

    return 0;
}