BOJ 14499 - 주사위 굴리기

14499번: 주사위 굴리기 (acmicpc.net)

 

NxM 크기의 지도에 주사위를 굴린다.

지도의 값이 0이면 주사위의 바닥면의 숫자가 지도로 복사되고 지도의 값이 0이 아니면 주사위의 바닥면에 지도의 숫자가 덮어씌워지며 지도의 숫자는 0이 된다.

매 이동시마다 주사위 상단에 쓰여 있는 값을 구하는 프로그램을 작성해라.

범위를 벗어나는 명령은 무시하라.

이동 명령에 따라 주사위의 바닥과 상단을 파악해야 한다.

초기에 바닥은 1이고 상단을 6 그리고 3이 동쪽을 바라보고 있는 상태이다.

주사위는 총 6개의 값을 가진 2차원 평면도로 표현할 수 있다.

[0, 2, 0]
[4, 1, 3]  
[0, 5, 0]
[0, 6, 0]

여기서 동, 서, 남, 북으로 이동을 평면도 상에서 표시해 보자. 동/서 와 남/북은 이동의 방향이 다르기 때문에 따로 생각해야 할 것 같다.

가로 방향 이동인 동쪽으로 3번 움직여보자. 4번 움직이면 원상복구 되니 규칙이 보일 것이다.

[0, 2, 0]     [0, 2, 0]     [0, 2, 0]     [0, 2, 0]
[4, 1, 3]     [1, 3, 6]     [3, 6, 4]     [6, 4, 1] 
[0, 5, 0]     [0, 5, 0]     [0, 5, 0]     [0, 5, 0]
[0, 6, 0]     [0, 4, 0]     [0, 1, 0]     [0, 3, 0]

규칙을 보면 1열이 좌로 1회 회전한 다음 [1][2] 와 [3][1]이 교환되는 형태이다.

1의 이동 : [1][1] → [1][0] → [3][1] → [1][2]

3의 이동: [1][2] → [1][1] → [1][0] → [3][1]

4의 이동: [1][0] → [3][1] →[1][2] → [1][1]

6의 이동: [3][1] → [1][2] → [1][1] → [1][0]

이렇게 4개의 위치가 반복되고 있다. 서쪽은 그저 화살표 방향이 반대인 것이다.

자세히 살펴보면 회전하고 있다는 것을 알 수 있다. [4, 1, 3, 6] 배열이 회전하는 것인데 마지막 위치의 숫자만 [3][1]에 존재하는 것이다.

이번에는 북쪽으로 3번 움직여보자

[0, 2, 0]     [0, 6, 0]     [0, 5, 0]     [0, 1, 0]
[4, 1, 3]     [4, 2, 3]     [4, 6, 3]     [4, 5, 3] 
[0, 5, 0]     [0, 1, 0]     [0, 2, 0]     [0, 6, 0]
[0, 6, 0]     [0, 5, 0]     [0, 1, 0]     [0, 2, 0]

북/남 이동도 역시 1열이 그냥 1칸씩 회전하는 것이다. 북쪽 이동은 아래로 1칸 회전, 남쪽 이동은 위로 1칸 이동이다.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static FastReader scan = new FastReader();
    static int N, M, initR, initC, K;
    static int[][] map;
    static int[] ORDERS; // 동쪽 1, 서쪽 2, 북쪽 3, 남쪽 4
    static final int[][] DIRECTION = {{0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}}; // x, 동, 서, 북, 남

    static class Dice {
        int[] row = new int[4];
        int[] col = new int[4];
        int r;
        int c;

        public Dice(int r, int c) {
            this.r = r;
            this.c = c;
        }

        public void move(int dir) {
            boolean rowMove = false;
            int nr = r + DIRECTION[dir][0];
            int nc = c + DIRECTION[dir][1];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M) return;

            if (dir == 1) {
                rotateLeft(row);
                rowMove = true;
            } else if (dir == 2) {
                rotateRight(row);
                rowMove = true;
            } else if (dir == 3) {
                rotateLeft(col);
            } else {
                rotateRight(col);
            }

            this.r = nr;
            this.c = nc;

            // 상,하 동기화
            if (rowMove) {
                col[1] = row[1];
                col[3] = row[3];
            } else {
                row[1] = col[1];
                row[3] = col[3];
            }

            // 회전해서 도착지에 도달한 상태 -> 업데이트 필요
            if (map[nr][nc] == 0) {
                map[nr][nc] = getBottom();
            } else {
                setBottom(map[nr][nc]);
                map[nr][nc] = 0;
            }

            System.out.println(getTop());
        }

        public int getTop() {
            return row[1];
        }

        public int getBottom() {
            return row[3];
        }

        public void setBottom(int value) {
            row[3] = value;
            col[3] = value;
        }

        private void rotateLeft(int[] arr) {
            // arr 왼쪽으로 1칸 회전
            reverse(arr, 0, arr.length - 1);
            reverse(arr, 0, arr.length - 2);
        }

        private void rotateRight(int[] arr) {
            // arr 오른쪽으로 1칸 회전
            reverse(arr, 0, arr.length - 1);
            reverse(arr, 1, arr.length - 1);
        }

        private void reverse(int[] arr, int from, int to) {
            while (from < to) {
                int tmp = arr[from];
                arr[from] = arr[to];
                arr[to] = tmp;
                from++;
                to--;
            }
        }
    }

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        initR = scan.nextInt();
        initC = scan.nextInt();
        K = scan.nextInt();

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = scan.nextInt();
            }
        }

        ORDERS = new int[K];
        for (int i = 0; i < K; i++) {
            ORDERS[i] = scan.nextInt();
        }
    }

    public static void main(String[] args) {
        input();
        Dice dice = new Dice(initR, initC);
        for (int dir : ORDERS) {
            dice.move(dir);
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}