[백준/23288/Java] 주사위 굴리기 2_초간단 설명

1. 문제 이해

백준의 삼성 문제집 문제들은 요구사항대로 코드를 완성시키기만 하면 대체로 테케는 다 통과가 되는 편입니다.

2. 문제 해석

스킵하겠습니다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m, k;
    static int[][] board;
    static int[] dx = {-1, 0, 1, 0};//up, right, down, left
    static int[] dy = {0, 1, 0, -1};//up, right, down, left

    public static void main(String[] args) throws IOException {
        init();

        Dice dice = new Dice();
        int x = 0, y = 0;
        int dir = 1;//start direction = right
        int answer = 0;

        while(k-- > 0) {
            if(!valid(x + dx[dir], y + dy[dir]))
                dir = reverseDir(dir);

            x = x + dx[dir];
            y = y + dy[dir];

            dice.rollDice(dir);

            answer += getScore(x, y);
            dir = getNextDir(dice.down, board[x][y], dir);
        }

        System.out.println(answer);

    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = pi(st.nextToken());
        m = pi(st.nextToken());
        k = pi(st.nextToken());
        board = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = pi(st.nextToken());
            }
        }
    }

    public static boolean valid(int x, int y) {
        if(x < 0 || x >= n || y < 0 || y >= m) return false;
        else return true;
    }

    public static int reverseDir(int dir) {
        return (dir+2)%4;
    }

    public static int getScore(int x, int y) {
        class Node {
            int x, y;

            public Node(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }

        //bfs
        boolean[][] visited = new boolean[n][m];
        visited[x][y] = true;
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x, y));

        int num = board[x][y];
        int count = 1;
        while(!queue.isEmpty()) {
            Node now = queue.poll();
            for (int dir = 0; dir < 4; dir++) {
                int nextX = now.x + dx[dir];
                int nextY = now.y + dy[dir];
                if (valid(nextX, nextY) && !visited[nextX][nextY] && board[nextX][nextY] == num) {
                    visited[nextX][nextY] = true;
                    count++;
                    queue.add(new Node(nextX, nextY));
                }
            }
        }

        return num * count;
    }

    public static int getNextDir(int diceBottom, int boardNum, int dir) {
        if(diceBottom > boardNum) {
            return (dir+1)%4;
        }
        else if(diceBottom < boardNum) {
            return (dir+3)%4;
        }
        else return dir;
    }

    public static int pi(String str) {
        return Integer.parseInt(str);
    }

    static class Dice{
        int up, down, left, right, front, back;
        public Dice() {
            up = 1; down = 6; left = 4; right = 3; front = 5; back = 2;
        }

        public void rollDice(int dir) {
            if(dir == 0) toNorth();
            else if(dir == 1) toEast();
            else if(dir == 2) toSouth();
            else toWest();
        }

        public void toEast() {
            int save = up;
            up = left;
            left = down;
            down = right;
            right = save;
        }

        public void toWest() {
            int save = up;
            up = right;
            right = down;
            down = left;
            left = save;
        }

        public void toNorth() {
            int save = up;
            up = front;
            front = down;
            down = back;
            back = save;
        }

        public void toSouth() {
            int save = up;
            up = back;
            back = down;
            down = front;
            front = save;
        }

//        public void print() {
//            System.out.println("  " + back + "  ");
//            System.out.println(left + " " + up + " " + right);
//            System.out.println("  " + front + "  ");
//        }
    }

}

4. 코드 해설

주사위 상태

• 주사위를 Dice 객체로 만들었습니다.
• Dice.rollDice(int dir) 메서드로 주사위를 회전합니다.
  • 각 회전에 따른 주사위 상태 변화는 코드를 참조해주세요.

메인 메서드

• init(): 입력으로부터 정보를 입력받습니다

• 초기 정보: 시작은 (0, 0) / 시작방향은 오른쪽입니다

• while문: k번 만큼 주사위를 옮깁니다

  • 방향대로 갔을 때 범위를 벗어나면, 방향을 반대로 바꿔줍니다
  • x, y를 업데이트합니다
  • dice.rollDice()로 주사위 상태를 바꿔줍니다
  • getScore()로 현재 칸의 점수를 획득합니다
  • getNextDir()로 주사위의 다음 방향을 설정합니다

핵심은 주사위 상태를 체크 + bfs로 해당 칸의 점수 얻기일텐데, 삼성 문제에서 2차원 배열의 dfs, bfs는 정말 자주 출제되니 꼭 알아두시면 좋을 것 같습니다!
주사위 상태 체크도 가끔 나오는데, 객체로 만들어서 관리하면 편리합니다.

다른 분들의 풀이를 보니, 미리 모든 칸에서 얻을 수 있는 점수를 배열로 구해놓는 방식으로 시간을 엄청 단축하신 분들이 있었습니다.
확실히 K가 커서 이미 방문했던 칸이나, 서로 연결된 칸들을 방문하는 경우가 많아지면 이런 풀이가 시간을 크게 줄여줄 것 같습니다.