븟츠의 주사위 굴리기 2(with Java) BOJ

Algorithm

븟츠의 주사위 굴리기 2(with Java) BOJ_23288

vtzs 2024. 7. 14. 00:12

문제 해석 😀

구현문제를 풀때 가장 중요한 것은 두가지이다.

1. 메서드 분리

메서드를 분리해야 디버깅을 하기 편함
각 메서드는 본인의 역할”에만” 충실할 것

2. 헷갈리지 않도록 심플하게 구현할 것

구현문제 ⇒ 보통 문제의 볼륨이 큼
주사위 굴리는 부분처럼 헷갈릴 수 있는 부분은 최대한 단순하게

나의 풀이 ✒

1. 주사위 객체가 메서드를 갖도록 하자

2. 점수를 미리 계산해두자

점수를 얻는 계산을 할때, 굴리고 점수 계산하고, 굴리고 점수 계산하지말고

한번에 DP 테이블을 계산을 다 해준 다음에, 주사위를 굴리면서 점수 계산을 하는 방향이 바람직하다고 생각했다.

적용 알고리즘 🎯

bfs, 완전탐색, 구현

나의 코드 💻

package BJ;

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

public class Problem23288 {
    static int N, M, K;
    static int[][] graph;
    static int[][] dp;
    static boolean[][] visited;
    // 동 남 서 북
    static int[][] vector = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static Queue<Point> queue = new LinkedList<>();
    static Set<Point> set = new HashSet<>();
    static Dice dice = new Dice(0, 0);
    static int result = 0;
    public static void main(String[] args) throws IOException {
        InputStreamReader ir = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(ir);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        graph = new int[N][M];
        dp = new int[N][M];
        visited = new boolean[N][M];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // fill dp table
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(!visited[i][j]){
                    queue.add(new Point(i, j));
                    set.add(new Point(i, j));
                    visited[i][j] = true;
                    int tempResult = bfs();
                    fillDP(tempResult);
                    set.clear();
                }
            }
        }
        // roll dice
        for(int i = 0; i < K; i++){
            dice.roll();
            result += dp[dice.x][dice.y];
        }
        System.out.println(result);
    }

    static void fillDP(int result){
        for(Point p : set){
            dp[p.x][p.y] = result;
        }
    }

    static int bfs(){
        Point p = queue.peek();
        int result = graph[p.x][p.y];
        int count = 1;
        while (!queue.isEmpty()){
            p = queue.poll();
            for(int[] v : vector){
                int nx = p.x + v[0];
                int ny = p.y + v[1];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if(visited[nx][ny]) continue;
                if(graph[p.x][p.y] == graph[nx][ny]){
                    count++;
                    visited[nx][ny] = true;
                    queue.add(new Point(nx, ny));
                    set.add(new Point(nx, ny));
                }
            }
        }
        result = result * count;
        return result;
    }

    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    static class Dice extends Point{
        int dir = 0;
        int up = 1;
        int down = 6;
        int left = 4;
        int right = 3;
        int front = 5;
        int back = 2;
        Dice(int x, int y) {
            super(x, y);
        }

        void roll(){
            move();
            changeNum();
            if(down > graph[x][y]){
                dir = (dir + 1) % 4;
            }
            else if(down < graph[x][y]){
                dir--;
                if(dir < 0) dir += 4;
            }
        }

        void move(){
            int nx = x + vector[dir][0];
            int ny = y + vector[dir][1];
            if(nx < 0 || nx >= N || ny < 0 || ny >= M){
                dir = (dir + 2) % 4;
                nx = x + vector[dir][0];
                ny = y + vector[dir][1];
            }
            x = nx;
            y = ny;
        }

        void changeNum(){
            int temp = down;
            if(dir == 0){
                down = right;
                right = up;
                up = left;
                left = temp;
            } else if(dir == 1){
                down = front;
                front = up;
                up = back;
                back = temp;
            } else if(dir == 2){
                down = left;
                left = up;
                up = right;
                right = temp;
            } else if(dir == 3){
                down = back;
                back = up;
                up = front;
                front = temp;
            }
        }
    }
}