백준 14499 주사위 굴리기

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

아이디어

• 주사위 뼈대는 그대로 놓고, 주사위에 쓰인 숫자를 이동 시키자

시간복잡도 계산

• 전체 명령에 대해 ; O(K)
• 주사위 이동 : O(4)
• 총합 : O(4K)

자료구조

• 전체 지도 : map[30][30]
• 주사위 : dice[4][3]

코드(C++)

#include <iostream>
 
using namespace std;
 
int map[30][30];
int dice[4][3];
int dy[] = {0,0,0,-1,1};
int dx[] = {0,1,-1,0,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 주사위 처음에 모든면이 0이 적혀있음
    fill(&dice[0][0], &dice[3][3], 0);
    
    int N,M,y,x,K; cin >> N >> M >> y >> x >> K;
    
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) cin >> map[j][i];
    }
    
    for(int k=0; k<K; k++) {
        int t; cin >> t;
        
        int ny = y + dy[t];
        int nx = x + dx[t];
        
        // 먼저 이동가능한지 먼저 확인
        if(!(ny>=0 && ny<N && nx>=0 && nx < M)) continue;
        
        y = ny;
        x = nx;
        
        // 주사위 이동
        if(t==1) {
            // 동쪽으로
            int tmp = dice[1][0];
            dice[1][0] = dice[3][1];
            dice[3][1] = dice[1][2];
            dice[1][2] = dice[1][1];
            dice[1][1] = tmp;
        } else if(t==2) {
            // 서쪽으로
            int tmp = dice[1][0];
            dice[1][0] = dice[1][1];
            dice[1][1] = dice[1][2];
            dice[1][2] = dice[3][1];
            dice[3][1] = tmp;
        } else if(t==3) {
            // 북쪽으로
            int tmp = dice[0][1];
            dice[0][1] = dice[1][1];
            dice[1][1] = dice[2][1];
            dice[2][1] = dice[3][1];
            dice[3][1] = tmp;
        } else if(t==4) {
            int tmp = dice[0][1];
            dice[0][1] = dice[3][1];
            dice[3][1] = dice[2][1];
            dice[2][1] = dice[1][1];
            dice[1][1] = tmp;
        }
        
        // 이동한 칸이 0인경우
        if(map[y][x] == 0) {
            map[y][x] = dice[3][1];
        } else {
            // 아닌경우
            dice[3][1] = map[y][x];
            map[y][x] = 0;
        }
        
        cout << dice[1][1] << '\n';
        
    }
    return 0;
}
 

문제유형

• 시뮬레이션 - 주사위 굴리기
  • 주사위나 큐브나, 회전해야되는 물체 있을때, 실제로 회전하는 것이 아니라 값들을 회전시킴