정육면체 한번 더 굴리기 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 시뮬레이션 + BFS

① 한 칸 전진해 점수 갱신 → ② 주사위 굴리고 방향 조정

1. 현재 방향으로 한 칸 전진하여 좌표 값을 갱신하고, 해당 칸에서 bfs를 통해 현재 칸에서 얻을 수 있는 점수를 구해 합을 갱신한다.

(한 칸 전진 시 격자판을 벗어난 경우, 반대 방향으로 되도록 조정해준다.)

 

2. 주사위가 놓인 상태를 조정한다. 이를 위해 현재 이동 방향에 맞춰 주사위를 굴리며 보이는 면 배열 dice를 갱신한다. 그리고 나서 주사위 바닥면의 값과 현재 칸의 값을 비교해 회전 방향을 조정한다.

    private static void rollDice() {
        // 1. 주사위 굴리기
        int[] tmp = dice.clone();
        if(dir == 0) {
            dice = new int[]{7 - tmp[2], tmp[1], tmp[0]};
        }
        else if(dir == 1) {
            dice = new int[]{7 - tmp[1], tmp[0], tmp[2]};
        }
        else if(dir == 2) {
            dice = new int[] {tmp[2], tmp[1], 7 - tmp[0]};
        }
        else if(dir == 3) {
            dice = new int[] {tmp[1], 7 - tmp[0], tmp[2]};
        }

        // 2. 주사위 바닥면 비교하기
        int bottom = 7 - dice[0];

        if(bottom > grid[x][y]) { // 시계 90도 회전
            dir = (dir + 1) % 4;
        }
        else if(bottom < grid[x][y]) {    // 반시계 90도 회전
            dir = (dir - 1 + 4) % 4;
        }
    }

 

 

💥 유의사항

BFS 진행 전 방문 배열은 매번 초기화해줘야 한다!!

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,1,0,-1};   // (시계 방향) 오른쪽 아래쪽 왼쪽 위쪽
    static int[] dy = {1,0,-1,0};
 
    static int n,m;
    static int[][] grid;
    static boolean[][] visited;
 
    static int[] dice = new int[] {1,2,3}; // 윗면 앞면 오른쪽면
    static int x = 0, y = 0, dir = 0;
    static int sum = 0;
 
    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());
 
        grid = new int[n][n];
        visited = new boolean[n][n];
 
        for(int i = 0 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine(), " "); 
            for(int j = 0 ; j < n ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }        
 
        while(m --> 0) {
            simulate();
        }
 
        System.out.println(sum);
    }
 
    private static void simulate() {
        // 1. 아랫면 확인해 방향 값 설정하기
        int nx = x + dx[dir];
        int ny = y + dy[dir];
 
        // 격자판 벗어난 경우 조정
        if(!inRange(nx, ny)) {
            dir = (dir + 2) % 4;
 
            nx = x + dx[dir];
            ny = y + dy[dir];
        }
 
        x = nx;
        y = ny;
        sum += bfs(x, y);
 
        // 2. 주사위 놓인 상태 조정하기
       rollDice();
    }
 
    private static void rollDice() {
        // 1. 주사위 굴리기
        int[] tmp = dice.clone();
        if(dir == 0) {
            dice = new int[]{7 - tmp[2], tmp[1], tmp[0]};
        }
        else if(dir == 1) {
            dice = new int[]{7 - tmp[1], tmp[0], tmp[2]};
        }
        else if(dir == 2) {
            dice = new int[] {tmp[2], tmp[1], 7 - tmp[0]};
        }
        else if(dir == 3) {
            dice = new int[] {tmp[1], 7 - tmp[0], tmp[2]};
        }
 
        // 2. 주사위 바닥면 비교하기
        int bottom = 7 - dice[0];
 
        if(bottom > grid[x][y]) { // 시계 90도 회전
            dir = (dir + 1) % 4;
        }
        else if(bottom < grid[x][y]) {    // 반시계 90도 회전
            dir = (dir - 1 + 4) % 4;
        }
    }
 
    private static int bfs(int x, int y) {
        for(int i = 0 ; i < n ; i++) { // 매번 초기화해줘야 함!! ⭐
            for(int j = 0 ; j < n ; j++)
                visited[i][j] = false;
        }
        visited[x][y] = true;
 
        int target = grid[x][y];
        int total = 0;
 
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
 
        while(!q.isEmpty()) {
            int[] now = q.poll();
            total += target;
 
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
 
                if(inRange(nx, ny) && !visited[nx][ny] && grid[nx][ny] == target) {
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny, total});
                }
            }
        }
 
        return total;
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < n);
    }
}

 

---

💦 어려웠던 점

- 이동시키고 주사위 굴리고 방향 전환하는 이 순서가 머리에서 뒤죽박죽이었다... 제대로 순서를 정리하고 하자...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리