[BOJ / C++] 주사위 굴리기 (시뮬레이션)

문제링크: https://www.acmicpc.net/problem/14499

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

void west(vector<vector<int>>& dice) {
    vector<vector<int>> tmp(4, vector<int>(3, 0));
    tmp[0][1] = dice[0][1];
    tmp[1][0] = dice[1][1];
    tmp[1][1] = dice[1][2];
    tmp[1][2] = dice[3][1];
    tmp[2][1] = dice[2][1];
    tmp[3][1] = dice[1][0];

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            dice[i][j] = tmp[i][j];
        }
    }
}

void south(vector<vector<int>>& dice) {
    vector<vector<int>> tmp(4, vector<int>(3, 0));
    tmp[0][1] = dice[3][1];
    tmp[1][0] = dice[1][0];
    tmp[1][1] = dice[0][1];
    tmp[1][2] = dice[1][2];
    tmp[2][1] = dice[1][1];
    tmp[3][1] = dice[2][1];

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            dice[i][j] = tmp[i][j];
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);

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

    vector<vector<int>> dice(4, vector<int>(3, 0));

    vector<vector<int>> board(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int num;
            cin >> num;
            board[i][j] = num;
        }
    }

    for (int i = 0; i < k; i++) {
        int op;
        cin >> op;

        if (op == 1) {
            if (y >= m-1) continue;
            y++;

            west(dice);
            west(dice);
            west(dice);

            if (board[x][y] == 0) {
                board[x][y] = dice[3][1];
            }
            else {
                dice[3][1] = board[x][y];
                board[x][y] = 0;
            }

            cout << dice[1][1] << '\n';
        }
        else if (op == 2) {
            if (y <= 0) continue;
            y--;

            west(dice);

            if (board[x][y] == 0) {
                board[x][y] = dice[3][1];
            }
            else {
                dice[3][1] = board[x][y];
                board[x][y] = 0;
            }

            cout << dice[1][1] << '\n';
        }
        else if (op == 3) {
            if (x <= 0) continue;
            x--;

            south(dice);
            south(dice);
            south(dice);

            if (board[x][y] == 0) {
                board[x][y] = dice[3][1];
            }
            else {
                dice[3][1] = board[x][y];
                board[x][y] = 0;
            }

            cout << dice[1][1] << '\n';
        }
        else if (op == 4) {
            if (x >= n-1) continue;
            x++;
            
            south(dice);

            if (board[x][y] == 0) {
                board[x][y] = dice[3][1];
            }
            else {
                dice[3][1] = board[x][y];
                board[x][y] = 0;
            }

            cout << dice[1][1] << '\n';
        }
    }
}

 

 

2. 시간복잡도

k = 1000이고, west, south 함수는 O(1)에 동작한다. 입력 시간복잡도는 n*m = 400이다.

전체 시간복잡도는 O(k)에 걸리고, 1000 < 10^8이므로 시간제한 2초 내에 통과 가능하다. 

 

 

3. 분석

 

무지성 빡구현을 진행했다. 주사위 전개도를 토대로 서쪽, 남쪽으로 굴렸을 때 위치를 위 사진과 같이 계산해본다. 이렇게 대응시키는 west, south 함수를 구현해준다. 그리고 북쪽 = 남쪽으로 3번 굴리기, 동쪽 = 서쪽으로 3번 굴리기로 계산했다. (귀찮기 때문이다. 회전 등의 구조에서 이런 식으로 구현 가능하다.) 

 

테스트 케이스가 각각 엣지케이스들을 포함하고 있다.

tc3에서는 주사위가 범위를 벗어나는 것에 대한 테스트를 하고있다.

tc4에서는 " 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 된다."에서 칸에 쓰여있는 수를 0으로 초기화하는지 확인한다.

 

tc4를 놓쳤었다. 문제를 꼼꼼히 읽어야한다.