[Algorithm] SW 기출문제 - 주사위 굴리기(14499) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 주사위 굴리기 자바 풀이를 작성하도록 하겠습니다.

 

문제 출처: https://www.acmicpc.net/problem/14499

14499번: 주사위 굴리기

 

 

1, 풀이 소스

 

import java.util.*;
import java.io.*;

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        int r = parseInt(st.nextToken());
        int c = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());

        Board board = new Board(n, m);
        board.setPoint(r, c);

        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++) {
                board.setMap(row, col, parseInt(st.nextToken()));
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            board.addCommand(parseInt(st.nextToken()));
        }

        board.run();
        System.out.print(board.printUpNumber());
    }
}

class Board {
    int n;
    int m;
    Point point;
    int[][] map;
    int[] dice;
    Queue<Character> cmds = new ArrayDeque<>();
    List<Integer> upNumbers = new ArrayList<>();

    Board (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m]; // (0, 0) 부터 시작
        dice = new int[6]; // front, bottom, back, up, left, right
    }

    void setPoint(int row, int col) {
        point = new Point(row, col);
    }

    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }

    void addCommand(int cmd) {
        switch (cmd) {
            case 1:
                cmds.add('E');
                break;
            case 2:
                cmds.add('W');
                break;
            case 3:
                cmds.add('N');
                break;
            case 4:
                cmds.add('S');
                break;
        }
    }

    void run() {

        while(!cmds.isEmpty()) {
            char command = cmds.poll();
            int row = 0;
            int col = 0;

            switch (command) {
                case 'E': // 동쪽은 열++
                    col++;
                    break;
                case 'W': // 서쪽은 열--
                    col--;
                    break;
                case 'N': // 북쪽은 행 -- (위로 올리므로)
                    row--;
                    break;
                case 'S': // 남쪽은 행 ++ (아래로 내려가므로)
                    row++;
                    break;
            }

            int nextR = point.row + row;
            int nextC = point.col + col;

            if (!isValid(nextR, nextC)) continue; // 유효하지 않은 명령어 패스

            rollDice(command); // 주사위 굴리기

            point.row = nextR; // 주사위 위치 row 이동시키기
            point.col = nextC; // 주사위 위치 col 이동시키기

            if (map[point.row][point.col] == 0) {
                map[point.row][point.col] = dice[1]; // 바닥에 주사위 값 복사
            } else {
                dice[1] = map[point.row][point.col]; // 바닥에 있는 값을 주사위애 복사
                map[point.row][point.col] = 0; // 칸 값 0
            }

            upNumbers.add(dice[3]); // 상단에 있는 주사위 값 upNumbers에 추가
        }
    }

    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < m;
    }

    void rollDice(char command) {
        // front(0), bottom(1), back(2), up(3), left(4), right(5) 회전 마침
        int up = dice[3];
        int bottom = dice[1];
        int left = dice[4];
        int right = dice[5];
        int front = dice[0];
        int back = dice[2];

        if (command == 'E') { // 왼쪽으로 회전
            dice[4] = up; // 왼 <- 위
            dice[1] = left; // 바 <- 왼
            dice[5] = bottom; // 오 <- 바
            dice[3] = right; // 위 <- 오
        }

        else if (command == 'W') { // 오른쪽으로 회전
            dice[5] = up; // 오 <- 위
            dice[1] = right; // 바 <- 오
            dice[4] = bottom; // 왼 <- 바
            dice[3] = left; // 위 <- 왼
        }

        else if (command == 'N') { // 북쪽으로
            dice[0] = bottom; // 앞 <- 바
            dice[3] = front; // 위 <- 앞
            dice[2] = up; // 뒤 <- 위
            dice[1] = back; // 바 <- 뒤
        }

        else if (command == 'S') {
            dice[0] = up; // 앞 <- 위
            dice[1] = front; // 바 <- 앞
            dice[2] = bottom; // 뒤 <- 바
            dice[3] = back; // 위 <- 뒤
        }
    }

    String printUpNumber() {
        StringBuilder sb = new StringBuilder();
        for (int num : upNumbers) sb.append(num).append("\n");
        return sb.toString();
    }

    class Point {
        int row;
        int col;

        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

 

 

2. 풀이 중점 사항

 

해당 문제는 회전 문제로, 주사위를 어떻게 회전시켜야 하는지가 중요한 과제입니다. 

먼저 방위표는 고정입니다. 즉 이전에 서쪽으로 이동하였더라도 방위표의 기준은 변하지 않습니다. 즉 서쪽 (컬럼 기준으로는 왼쪽으로 이동) 방향은 바뀌지 않습니다.

 

현재 위치한 지점으로 부터 동서남북 각 방향으로 이동한다고 했을 때, 명령어에 따라 주사위를 회전시켜야 합니다.

이후, 회전시킨 주사위를 이동시켜서 칸에 번호가 있는지 없는지 판단하고 바닥을 업데이트해야 합니다.

 

문제 풀이 의사코드는 다음과 같습니다.

 

• 각 방위에 대한 숫자형 데이터를 입력받고, 선호도에 따라 인트형 혹은 char형 등으로 이동 방향을 선입선출로 처리할 큐에 넣습니다.
• 큐가 빌 때까지 (방향) 루프를 진행합니다.
• 각 방위는 고정이므로 E, W, N, S에 따라 다음 이동할 nextR, nextCol을 조정합니다.
• 이동 불가능한 (인덱스를 벗어난) nextR, nextCol은 continue 하여 명령어를 넘깁니다.
• 이동 가능한 경우 rollDice()를 통해 주사위를 굴려서 각 주사위의 값을 회전시킵니다.
• 회전 시, 동 서 방향은 위, 바닥, 왼쪽, 오른쪽 면만 영향을 받습니다.
• 회전 시, 남 북 방향은 앞, 뒤, 위, 바닥 면만 영향을 받습니다.
• 회전을 마친 후, 구한 nextR, nextC을 현재 있는 point에 업데이트하여 이동을 시작합니다.
• 이동한 칸이 0이라면, 현재 주사위 상태의 바닥에 있는 값을 칸에 복사합니다.
• 이동한 칸이 0이 아니라면, 현재 주사위 상태의 바닥에 칸의 값을 복사하고, 칸은 0으로 만듭니다.
• 이동을 마쳤으므로 현재 주사위 상태의 윗면의 값을 upNumbers에 추가합니다.
• 큐가 비면, 윗면 리스트를 담은 upNumbers를 출력합니다.

 

방향성 

 

switch (command) {
    case 'E': // 동쪽은 열++
        col++;
        break;
    case 'W': // 서쪽은 열--
        col--;
        break;
    case 'N': // 북쪽은 행 -- (위로 올리므로)
        row--;
        break;
    case 'S': // 남쪽은 행 ++ (아래로 내려가므로)
        row++;
        break;
}

 

저는 이전에 이러한 이동 문제를 풀 때, x, y로 하려다 보니 항상 실수했던 경험이 있습니다. 따라서, row, col로 명확하게 명시하고 문제를 해결하다 보니 DB를 다룰 때처럼 자연스럽게 up 명령어는 row--를 실행하고 down 명령어는 row++를 처리하여 도중에 실수를 방지할 수 있었습니다.

 

 

주사위 회전

 

if (command == 'E') { // 왼쪽으로 회전
    dice[4] = up; // 왼 <- 위
    dice[1] = left; // 바 <- 왼
    dice[5] = bottom; // 오 <- 바
    dice[3] = right; // 위 <- 오
}

 

주사위 회전 시, 저는 이 부분이 항상 헷갈렸습니다. 따라서 저는 command == 'E'라는 식으로 명확하게 동쪽으로 회전하겠다는 것을 명시하여 혼돈을 줄이도록 작성을 했습니다.

왼쪽으로 주사위를 돌리면, 위쪽에 있던 면은 왼쪽으로 가므로 이러한 방식으로 회전을 처리하였습니다.

 

작성하다 보니 코드가 길어졌지만, 문제 자체가 난해하고 어렵기 때문에,

케이스를 명확하게 나누는 연습을 하였고, 쓰다가 제가 헷갈리는 것을 방지하기 위해 이왕이면 코드가 의미하는 바가 무엇인지 최대한 신경 써서 작성하려고 하였습니다.

 

이상으로 주사위 굴리기 문제를 마치도록 하겠습니다. 감사합니다.!