백준 14499

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

Intuition

문제 자체가 그렇게 이해하기 어렵진 않아서 주사위를 이동하는 것만 잘 구하면 된다고 생각했다.

Approach

어느방향으로 움직이더라도 특정 면이 아래에 있을때 동서남북에 오는 면이 고정될 것이라 생각했는데 아니었다. 이걸로 30분 날렸다

top_n이 하늘을 바라보는 면, ns 가 top_n 기준으로 북쪽에 있는 면으로 한다.

특정 면을 기준으로 북쪽에 어떤 면에 있는지에 따라 동 서에 오는 면이 달라지므로 이를 넣었다.

예를들어 top_n = 1, ns = 2라면 동쪽으로 움직일때 top_n이 4, 6, 3, 1 ~~ 원형으로 변한다.

 

// 1 -> 5 4 2 3
// 2 -> 1 4 6 3
// 3 -> 5 1 2 6
// 4 -> 6 2 1 5
// 5 -> 3 6 4 1
// 6 -> 3 2 4 5

이를 다음과 같이 계산해서 이차원 배열에 넣었다. (ns -> 동쪽으로 갈때 나오는 면)

 

북쪽으로 움직이면 top_n = 주사위 기준 ns의 반대쪽 면, ns = top_n

남쪽으로 움직이면 top_n = ns, ns = top_n의 반대쪽 면

과 같이 계산해서 넣어줬다.

Complexity

- Time complexity : O(K)

- Space complexity : O(NM + a)

Code

#include <iostream>

using namespace std;
int N,M, x, y, K, board[21][21], dice[7], dice_r[7]={0,6,5,4,3,2,1}, dx[5]={0,0,0,-1,1}, dy[5]={0,1,-1,0,0};
int d[7][4] = {
{0,0,0,0},{5,4,2,3}, {1,4,6,3},{5,1,2,6},{6,2,1,5},{3,6,4,1},{3,2,4,5}};
// 1 -> 5 4 2 3
// 2 -> 1 4 6 3
// 3 -> 5 1 2 6
// 4 -> 6 2 1 5
// 5 -> 3 6 4 1
// 6 -> 3 2 4 5


int main(){
    //initiate
     cin>>N>>M>>x>>y>>K;
     for (int i=0; i<N; i++)
         for (int j=0; j<M; j++)
             cin>>board[i][j];


    int top_n = 1, ns = 2;
    // 동서로 움직이면 ns 그대로
    // 북으로 움직이면 top_n = dice_r[ns], ns = top_n
    // 남으로 움직이면 top_n = ns, ns = dice_r[top_n]
    for (int i=0; i<K; i++) {
        int dir; cin>>dir;
        int nx = x + dx[dir], ny = y + dy[dir];
        if (nx >= N || nx < 0 || ny >= M || ny < 0) continue;
        x = nx; y = ny;
        if (dir == 3) {
            int top_n_tmp = top_n;
            top_n = dice_r[ns];
            ns = top_n_tmp;
        }else if (dir == 4) {
            int ns_tmp = ns;
            ns = dice_r[top_n];
            top_n = ns_tmp;
        }else {
            for (int i=0; i<4; i++) {
                if (top_n == d[ns][i]) {
                    if (dir == 1) {
                        i += 1;
                        i %= 4;
                        top_n = d[ns][i];
                    }
                    if (dir == 2) {
                        i -= 1;
                        if (i == -1) i += 4;
                        top_n = d[ns][i];
                    }
                    break;
                }
            }
        }
        cout<<dice[top_n]<<endl;
        if (board[x][y]) {
            dice[dice_r[top_n]] = board[x][y];
            board[x][y] = 0;
        }else {
            board[x][y] = dice[dice_r[top_n]];
        }
    }

}