백준 23288번: 주사위 굴리기 2 (Java)

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

23288번: 주사위 굴리기 2

 

 

 

 

 

 

 

 

---

 

풀이

는 딱히 할 말이 없네요. 문제에서 주어진 조건대로 구현을 하면 됩니다.

 

자잘한 팁

예시의 4x5 지도에서 주사위가 1000번 구르는 상황을 생각해보면, 같은 위치에 대해 여러 번 점수를 구할 겁니다(비둘기집 원리: 50번 이상 점수를 계산하게 되는 칸이 존재함). 이를 전처리로 구해두면 실행 속도가 빨라집니다. 아래 코드에서는 scoreMap이라는 이차원 int 배열에 각 칸 별 점수를 기록해두었습니다. 혹은, 매번 dfs로 접근하되 memoizaiton하는 방법도 있을 겁니다.

주사위가 구르는 것에 대한 구현을, 가지수가 4개밖에 없으니 각 방향마다 하드코딩해도 됩니다. 다만, 방향에 따라 돌리는 면을 index로 지정하여 구현하면 코드가 깔끔해지며, 실수를 줄일 수 있습니다. 더 나아가, 돌리는 면을 변수명으로 지정해주면 코드가 더욱 보기 좋아집니다(케로츄님 코드를 참고했습니다).

'시계/반시계 방향으로 90도 회전'와 같은 구현은 적당히 방향을 시계방향/반시계방향 순으로 정해두고(문제에서 방향이 숫자로 입력이 주어지면 그대로 하고, 아닌 경우는 맘대로) (방향+1)%4, (방향+3)%4와 같은 방식으로 하면 편합니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static Dice dice;
    // 각 주사위 면을 지정하는 index를 final 변수로 설정
    // 실수를 줄이기 좋은 표기법
    static final int UP = 0, FRONT = 1, DOWN = 2, BACK = 3, LEFT = 4, RIGHT = 5;
    static int[] dr = { 0, 1, 0, -1 };
    static int[] dc = { 1, 0, -1, 0 };
    static int N, M;
    static int[][] map, scoreMap;
    static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        map = new int[N+1][M+1];
        scoreMap = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 각 위치별 점수를 미리 구하기
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (!visited[i][j]) {
                    getScoreMap(i, j);
                }
            }
        }
        
        dice = new Dice(1, 1, 0, new int[] {1, 5, 6, 2, 4, 3});
        int ans = 0;
        while (K-- > 0) {
            move();
            ans += getScore();
            decideDir();
        }
        System.out.println(ans);
    }
    
    // 주사위를 움직이며, 굴리는 method
    static void move() {
        int nr = dice.r + dr[dice.dir], nc = dice.c + dc[dice.dir];
        if (nr <= 0 || nr > N || nc <= 0 || nc > M) {
            dice.dir = (dice.dir + 2) % 4;
            nr = dice.r + dr[dice.dir];
            nc = dice.c + dc[dice.dir];
        }
        switch (dice.dir) {
        case 0:
            dice.roll(UP, LEFT, DOWN, RIGHT);
            break;
        case 1: 
            dice.roll(UP, BACK, DOWN, FRONT);
            break;
        case 2:
            dice.roll(UP, RIGHT, DOWN, LEFT);
            break;
        case 3:
            dice.roll(UP, FRONT, DOWN, BACK);
            break;
        }
        dice.r = nr;
        dice.c = nc;
    }
    
    // 점수를 구하는 method
    static int getScore() {
        return scoreMap[dice.r][dice.c];
    }
    
    // 방향을 정하는 method
    static void decideDir() {
        int down = dice.status[2];
        if (down > map[dice.r][dice.c]) {
            dice.dir = (dice.dir + 1) % 4;
        } else if (down < map[dice.r][dice.c]) {
            dice.dir = (dice.dir + 3) % 4;
        } 
    }
    
    static void getScoreMap(int i, int j) {
        Queue<int[]> queue = new ArrayDeque<>();
        Queue<int[]> queue2 = new ArrayDeque<>();
        queue.offer(new int[] {i, j});
        queue2.offer(new int[] {i, j});
        visited[i][j] = true; 
        int cnt = 1;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            for (int dir = 0; dir < 4; dir++) {
                int nr = r + dr[dir], nc = c + dc[dir];
                if (nr <= 0 || nr > N || nc <= 0 || nc > M) continue;
                if (visited[nr][nc] || map[nr][nc] != map[i][j]) continue;
                visited[nr][nc] = true;
                cnt++;
                queue.offer(new int[] {nr, nc});
                queue2.offer(new int[] {nr, nc});
            }
        }
        while (!queue2.isEmpty()) {
            int[] cur = queue2.poll();
            int r = cur[0], c = cur[1];
            scoreMap[r][c] = cnt*map[i][j];
        }
    }
    
    // 주사위 class: 위치, 방향, 면 상태를 저장한다.
    static class Dice {
        int r, c, dir;
        int[] status = new int[6];
        
        public Dice(int r, int c, int dir, int[] status) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.status = status;
        }
        
        void roll(int a, int b, int c, int d) {
            int temp = status[a];
            status[a] = status[b];
            status[b] = status[c];
            status[c] = status[d];
            status[d] = temp;
        }
    }
}