[BOJ/Java] 23288: 주사위 굴리기 2

문제

https://www.acmicpc.net/problem/23288

크기가 N x M인 지도가 있다. 지도 상의 정보는 정수로 주어진다.

 

이 지도 상에는 주사위가 하나 있다. 주사위의 전개도(주사위의 처음 상태)는 다음과 같다. 1이 주사위의 윗면이다.

  2
4 1 3
  5
  6

 

지도 상의 주사위 이동은 다음과 같이 진행된다.

 

1. 이동 방향으로 한 칸 구른다. 이동했을 때 칸이 없다면 현재 이동 방향의 반대 방향으로 구른다.

2. 주사위가 도착한 (x, y) 상의 좌표에 대한 점수를 획득한다. 이때 점수는 주사위의 현재 좌표의 숫자와 숫자가 동일한, 인접해서 연속으로 이동할 수 있는 칸의 수를 모두 더한 값이다.

3. 주사위의 아랫면에 있는 정수와 주사위가 도착한 칸의 정수를 비교해 이동 방향을 결정한다.

 

1~1,000번 이동했을 때 획득할 수 있는 점수를 계산하면 된다.

 

풀이

처음엔 한 번 이동 시 연속으로 이동하며 결과값을 반환하는 함수를 구현하려고 했다. 그런데 move 함수에서 BFS로 이동하려니 한 번 이동에 여러 번 움직이는 코드가 되었다. move 함수에서 점수를 계산하는 로직을 분리하여 move 함수는 새로운 좌표를 계산하고 주사위를 굴리도록 변경해주었다. 점수 계산을 위해서는 한 번 이동 후 해당 좌표를 기준으로 그래프를 탐색해주어야 하기 때문에 이쪽이 더 적절한 로직이라고 생각된다.

 

점수를 계산하는 로직도 문제 설명과 아예 달랐다는 점. 문제를 처음 봤을 땐, 이동하는 방향에 따라 모든 칸의 수를 더하는 줄 알았지만, 다시 보니 현재 칸과 동일한 숫자의 칸을 모두 방문해서 더하는 것이 한 번 이동했을 때의 점수였다. 문제를 자세히 읽는 연습이 필요할 것 같다.

 

또 다른 문제는 주사위를 굴리는 로직에서 발생했다. 주사위의 전개도가 가로축, 세로축을 기준으로 일정한 패턴으로 움직이고 있어 조작하기 쉽도록 이차원 배열로 저장했는데, 주사위를 굴렸을 때 가로축과 세로축이 겹치는 주사위의 윗면이 동기화되어 변경되지 않으면서 예상치 못했던 문제가 발생했다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, m, k;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] dice = {
            {4, 1, 3}, // 전개도의 가로축
            {2, 5}, // 전개도의 세로축
            {6} // 전개도 상의 주사위 아랫면
    };
    static int x, y = 0;
    static int dir = 0; // 동, 남, 서, 북

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int point = 0;
        // k번 이동한다.
        // 1. 이동 방향으로 한 칸 구른다. 만약 막혀있을 경우, 반대로 이동한다.
        // 2. 해당 칸의 점수를 획득한다.
        // 3. 주사위의 아랫면의 수와 해당 칸의 수를 비교해 이동 방향을 결정한다.
        while (k-- > 0) {
            move(); // 이동한다.
            
            point += getScore(x, y); // 이동 후 얻을 수 있는 점수를 계산한다.
            
            // 다음 이동 방향을 결정
            int bottom = dice[2][0]; // 주사위 아랫면 숫자
            int cell = map[x][y]; // 현재 칸의 숫자

            if (bottom > cell) {
                dir = (dir + 1) % 4;
            } else if (bottom < cell) {
                dir = (dir + 3) % 4;
            }
        }

        System.out.println(point);
    }

    public static void move() {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
            dir = (dir + 2) % 4;
            nx = x + dx[dir];
            ny = y + dy[dir];
        }

        x = nx;
        y = ny;
        
        roll();
    }

    public static void roll() {
        int temp = dice[2][0];
        switch (dir) {
            // 동, 남, 서, 북
            case 0:
                dice[2][0] = dice[0][2]; // 아랫면
                dice[0][2] = dice[0][1];
                dice[0][1] = dice[0][0];
                dice[0][0] = temp;
                break;
            case 1:
                dice[2][0] = dice[1][1];
                dice[1][1] = dice[0][1];
                dice[0][1] = dice[1][0];
                dice[1][0] = temp;
                break;
            case 2:
                dice[2][0] = dice[0][0];
                dice[0][0] = dice[0][1];
                dice[0][1] = dice[0][2];
                dice[0][2] = temp;
                break;
            case 3:
                dice[2][0] = dice[1][0];
                dice[1][0] = dice[0][1];
                dice[0][1] = dice[1][1];
                dice[1][1] = temp;
                break;
        }
    }

    static int getScore(int startX, int startY) {
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> queue = new ArrayDeque<>();
        int value = map[startX][startY];
        int count = 1;

        visited[startX][startY] = true;
        queue.offer(new int[]{startX, startY});

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentX = current[0];
            int currentY = current[1];

            for (int d = 0; d < 4; d++) {
                int newX = currentX + dx[d];
                int newY = currentY + dy[d];

                if (newX < 0 || newY < 0 || newX >= n || newY >= m) continue;
                if (visited[newX][newY]) continue;
                if (map[newX][newY] != value) continue;

                visited[newX][newY] = true;
                count++;
                queue.offer(new int[]{newX, newY});
            }
        }

        return count * value;
    }

}

 

오답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, m, k, point;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 1, 0, -1}; // 동, 남, 서, 북
    static int[] dy = {1, 0, -1, 0};
    static int[][] dice = {{4, 1, 3}, {2, 1, 5}, {6}};

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // k번 이동한다.
        // 1. 이동 방향으로 한 칸 구른다. 만약 막혀있을 경우, 반대로 이동한다.
        // 2. 해당 칸의 점수를 획득한다.
        // 3. 주사위의 아랫면의 수와 해당 칸의 수를 비교해 이동 방향을 결정한다.
        while (k-- > 0) {
            // 첫 번째 이동은 동쪽
            point += map[0][1];
            move(0, 1, 1, changeBottomOfDice(1));
        }

        System.out.println(point);
    }

    public static void move(int startX, int startY, int startDir, int bottom) {
        Queue<Node> queue = new ArrayDeque<>();
        visited = new boolean[n][m];

        visited[startX][startY] = true;
        queue.add(new Node(startX, startY, startDir, bottom));

        while (!queue.isEmpty()) {
            Node current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int newX = current.x + dx[i];
                int newY = current.y + dy[i];

                if (newX < 0 || newX >= n || newY < 0 || newY >= m) {
                    int newDir = (current.dir + 2) % 4;
                    int newBottom = changeBottomOfDice(newDir);
                    newX = current.x + dx[newDir];
                    newY = current.y + dy[newDir];
                    point += map[newX][newY];
                    queue.add(new Node(newX, newY, newDir, newBottom));
                }
                if (bottom > map[newX][newY]) {
                    // 이동 방향을 90도 시계 방향으로 회전
                    int newDir = (current.dir + 1) % 4;
                    int newBottom = changeBottomOfDice(newDir);
                    point += map[newX][newY];
                    queue.add(new Node(newX, newY, newDir, newBottom));
                } else if (bottom < map[newX][newY]) {
                    // 이동 방향을 90도 반시계 방향으로 회전
                    int newDir = current.dir == 1 ? 4 : current.dir - 1;
                    int newBottom = changeBottomOfDice(newDir);
                    point += map[newX][newY];
                    queue.add(new Node(newX, newY, newDir, newBottom));
                } else {
                    // 이동 방향에 변화 없음
                    int newBottom = changeBottomOfDice(current.dir);
                    point += map[newX][newY];
                    queue.add(new Node(newX, newY, current.dir, newBottom));
                }
            }
        }
    }

    public static int changeBottomOfDice(int dir) {
        int temp = dice[2][0];
        switch (dir) {
            // 동, 남, 서, 북
            case 0:
                dice[2][0] = dice[0][2]; // 아랫면
                dice[0][2] = dice[0][1];
                dice[0][1] = dice[0][0];
                dice[0][0] = temp;
                break;
            case 1:
                dice[2][0] = dice[1][2];
                dice[1][2] = dice[1][1];
                dice[1][1] = dice[1][0];
                dice[1][0] = temp;
                break;
            case 2:
                dice[2][0] = dice[0][0];
                dice[0][0] = dice[0][1];
                dice[0][1] = dice[0][2];
                dice[0][2] = temp;
                break;
            case 3:
                dice[2][0] = dice[1][0];
                dice[1][0] = dice[1][1];
                dice[1][1] = dice[1][2];
                dice[1][2] = temp;
                break;
        }
        return dice[2][0];
    }

    public static class Node {
        int x;
        int y;
        int dir;
        int bottom;

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


}