[백준][Java] 23288 - 주사위 굴리기 2

목차

문제 정보

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

23288번: 주사위 굴리기 2

난이도 :  G3

유형 : 시뮬레이션, BFS, 해쉬

 

---

문제 풀이

[핵심]

1. 매번 주사위가 움직일 때마다 주사위의 6면 상태를 관리

2. 매번 이동 방향의 인덱스(dirIdx)를 알맞게 조정

 

[최적화]

매번 점수를 구할 때 항상 탐색을 하면 비효율적이다.

 

해쉬맵을 이용하여 BFS 탐색 종료 후

탐색되었던 곳들을 하나의 그룹번호로 묶고 해당 그룹의 총점수를 해쉬맵에 저장한다. HashMap(그룹번호, 해당 그룹의 총점수)

 

후에 주사위가 이동하면서 만약 그룹번호가 적힌 곳이라면 해쉬맵에서 값을 가져오면 되고

그룹 번호가 적혀있지 않다면 탐색을 한 적이 없던 곳이기 때문에  BFS탐색을 진행하면 된다.

---

코드

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

/**
 * BOJ_23288
 * author_devteo77
 */

public class Main {

    final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int N;
    int M;
    int K;
    int[][] board;
    HashMap<Integer, Integer> groupHash;
    int groupNumber;
    int[][] groupBoard;
    int res;

    public boolean validateRange(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= M) {
            return false;
        }
        return true;
    }

    public int getNextDirIdx(int bottom, int value, int dirIdx) {
        if (bottom > value) {
            return (dirIdx + 1) % 4;
        } else if (bottom < value) {
            dirIdx--;
            if (dirIdx < 0) {
                dirIdx = 3;
            }
            return dirIdx;
        }
        return dirIdx;
    }

    public int execBFS(int x, int y) {
        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[]{x, y});
        groupBoard[x][y] = groupNumber;
        int value = board[x][y];

        while (!que.isEmpty()) {
            int[] cur = que.poll();

            for (int i = 0; i < dir.length; i++) {
                int nX = cur[0] + dir[i][0];
                int nY = cur[1] + dir[i][1];

                if (!validateRange(nX, nY)) {
                    continue;
                }

                if (board[nX][nY] == board[x][y] && groupBoard[nX][nY] == 0) {
                    que.add(new int[]{nX, nY});
                    groupBoard[nX][nY] = groupNumber;
                    value += board[nX][nY];
                }
            }
        }

        groupHash.put(groupNumber++, value);
        return value;
    }

    public void solution() 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());
        K = Integer.parseInt(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] = Integer.parseInt(st.nextToken());
            }
        }

        groupNumber = 1;
        groupBoard = new int[N][M];
        groupHash = new HashMap<>();
        res = 0;
        Dice dice = new Dice();

        while (K-- > 0) {
            if (!validateRange(dice.x + dir[dice.dirIdx][0], dice.y + dir[dice.dirIdx][1])) {
                dice.dirIdx = (dice.dirIdx + 2) % 4;
            }

            dice.x = dice.x + dir[dice.dirIdx][0];
            dice.y = dice.y + dir[dice.dirIdx][1];

            dice.roll(dice.dirIdx);

            if (groupBoard[dice.x][dice.y] != 0) {
                res += groupHash.get(groupBoard[dice.x][dice.y]);
            } else {
                res += execBFS(dice.x, dice.y);
            }

            dice.dirIdx = getNextDirIdx(dice.bottom, board[dice.x][dice.y], dice.dirIdx);
        }

        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static class Dice {
        int dirIdx;
        int x;
        int y;
        int top;
        int bottom;
        int left;
        int right;
        int up;
        int down;

        public Dice() {
            this.dirIdx = 0;
            this.x = 0;
            this.y = 0;
            this.top = 1;
            this.bottom = 6;
            this.left = 4;
            this.right = 3;
            this.up = 2;
            this.down = 5;
        }

        public void moveEast() {
            int temp = bottom;
            bottom = right;
            right = top;
            top = left;
            left = temp;
        }

        public void moveSouth() {
            int temp = bottom;
            bottom = down;
            down = top;
            top = up;
            up = temp;
        }

        public void moveWest() {
            int temp = bottom;
            bottom = left;
            left = top;
            top = right;
            right = temp;
        }

        public void moveNorth() {
            int temp = bottom;
            bottom = up;
            up = top;
            top = down;
            down = temp;
        }

        public void roll(int dirIdx) {
            if (dirIdx == 0) {
                moveEast();
            } else if (dirIdx == 1) {
                moveSouth();
            } else if (dirIdx == 2) {
                moveWest();
            } else {
                moveNorth();
            }
        }
    }
}