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

문제 해석 😀

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

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;
            }
        }
    }
}

문제 풀이 설명 🎉

1. 입력(생략)

2. DP 테이블 채우기

점수는 이미 정해져있다!

위 처럼 점수는 이미 정해져있다.

어떻게?

1. 방문하지 않았으면 같은 점수 값만 방문하도록 bfs 시행
2. 방문했던 좌표값을 기억해야함 ⇒ 같은 숫자의 칸이 몇개 있을지 모르니까 ! 몇개의 칸이 있는지 센 다음, 점수를 계산하고, 해당 방문한 좌표값에 채워주기 ⇒ set 자료구조 이용

3. 주사위 굴리기 시뮬레이션

3-1. Point 객체를 상속받은 Dice 객체

• x, y 좌표값, 현재 진행방향(dir), 6면에 각각 어떤 값이 있는지

3-2. roll 메서드

주사위가 굴러가는 행동은

1. 움직이고 ⇒ move 메서드
2. 6면의 값이 바뀌고 ⇒ changeNum();
3. 방향이 변경되고 ⇒ if 문
   1. 주사위의 밑면과, graph의 값에 따라서 방향 시계방향으로 또는 반시계방향으로 변경되도록 구현
    

3-2-1) move 메서드

1. 좌표값을 방향에 맞게 옮기고
2. 만약 맵 밖으로 나갔다면 문제 조건에 맞게 방향을 변화 시키기

3-2-2) changeNum 메서드

• 진행 방향에 맞게 각 면들의 값을 옮겨주면 된다.

4. 점수 계산

1. K번 주사위를 굴린다 ⇒ dice의 roll 메서드
   1. 움직이고 ⇒ move 메서드
   2. 각 면의 값 변화 ⇒ changeNum 메서드
2. 결과를 더해준다
3. 출력한다

실행 결과 🎁