백준 23288

🎲 백준 23288 주사위 굴리기 2

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

23288번: 주사위 굴리기 2

🎲 어릴때부터 이런 입체도형 계산하는 문제를 유구하게 못했는데 ..주사위 돌아가는거 생각하는게 헷갈렸다ㅎ 

🎲 주사위 돌아가는 부분을 이 블로그를 보고 힌트를 얻었다.

 

🎲 주사위

🎲 주사위 자체를 현재 방향에 따라 위 이미지처럼 계속 돌려가면서, 아랫면 (dice[3][1]) 만 점수 비교하는데 쓰면 된다. 

 

🎲 자료구조

private static int row, col, move, answer, currentDir;
private static Pos curPos;
private static int[] dirX = { 0, 1, 0, -1};
private static int[] dirY = { 1, 0, -1, 0};
private static int[][] dice = {
        {0, 2, 0},
        {4, 1, 3},
        {0, 5, 0},
        {0, 6, 0}
};
private static int[][] map;

🎲 메인 로직

🎲 firstMove : 현재 위치에서 방향 결정한 다음 이동.

• nextX, nextY 찾아서 이동시키고, 방향(currentDir)도 유효하지 않은 방향이면 뒤집어주기 
• 그 후, nextX, nextY 기준으로 getScore(), findNextDir() 호출하기 

private static void firstMove() {
    int nextX = curPos.x + dirX[currentDir];
    int nextY = curPos.y + dirY[currentDir];

    if (!isValid(nextX, nextY)) {
        nextX = curPos.x + dirX[(currentDir + 2) % 4];
        nextY = curPos.y + dirY[(currentDir + 2) % 4];
        currentDir = (currentDir + 2) % 4;
    }

    curPos = new Pos(nextX, nextY);
    getScore(nextX, nextY);
    findNextDir(nextX, nextY);
}

 

 

🎲 getScore() : 해당 좌표의 점수, 그리고 findLen 함수 호출을 통해 갈 수 있는 칸 수 계산한다음 해당 칸에서의 점수 계산하기

private static void getScore(int x, int y) {
    int score = map[x][y];
    int len = findLen(x, y, score);
    answer += score * len;
}

 

🎲 findLen() : BFS 방식 구현

• 헷갈렸던게 갈 수 있는 경로라고 생각했는데, 이동할 수 있는 칸의 개수를 세는 것이다. 
• 경로라 생각하고 DFS로 하면 중간 테스트 케이스 틀리는 게 생긴다. 
• 종단점이 있는게 아니고 연결된 블록 찾는거라 BFS가 문제 취지에 더 맞을 것 같다. 

private static int findLen(int x, int y, int score) {
    boolean[][] temp = new boolean[row][col];
    int len = 0;
    Queue<Pos> queue = new LinkedList<>();
    queue.add(new Pos(x, y));
    temp[x][y] = true;

    while (!queue.isEmpty()) {
        Pos pop = queue.poll();
        len++;
        for (int i = 0; i < 4; i++) {
            int nextX = pop.x + dirX[i];
            int nextY = pop.y + dirY[i];

            if (!isValid(nextX, nextY)) {
                continue;
            }

            if (map[nextX][nextY] != score) {
                continue;
            }

            if (temp[nextX][nextY]) {
                continue;
            }

            queue.add(new Pos(nextX, nextY));
            temp[nextX][nextY] = true;
        }
    }
    return len;
}

 

 

🎲 findNextDir() : 다음 방향을 찾는다. 

• 여기서 맨 처음 그린 주사위 계산 작업이 나온다. 
• 현재 방향에 맞게 주사위 아랫면을 계산해주고, map에 있는 score와 비교하여 방향을 재조정해준다. 

private static void findNextDir(int x, int y) {
    // 현재 주사위 아랫면 구하기
    switch (currentDir) {
        case 0 :
            int temp = dice[1][2];
            dice[1][2] = dice[1][1];
            dice[1][1] = dice[1][0];
            dice[1][0] = dice[3][1];
            dice[3][1] = temp;
            break;
        case 1 :
            temp = dice[3][1];
            dice[3][1] = dice[2][1];
            dice[2][1] = dice[1][1];
            dice[1][1] = dice[0][1];
            dice[0][1] = temp;
            break;
        case 2 :
            temp = dice[1][0];
            dice[1][0] = dice[1][1];
            dice[1][1] = dice[1][2];
            dice[1][2] = dice[3][1];
            dice[3][1] = temp;
            break;
        case 3 :
            temp = dice[0][1];
            dice[0][1] = dice[1][1];
            dice[1][1] = dice[2][1];
            dice[2][1] = dice[3][1];
            dice[3][1] = temp;
            break;
    }

    int a = dice[3][1];
    if (a > map[x][y]) {
        currentDir = (currentDir + 1) % 4;
    } else if (a < map[x][y]) {
        currentDir = (currentDir + 3) % 4;
    }
}

 

---

 

🎲 전체코드 

import java.util.*;
import java.io.*;
public class p23288 {
    private static int row, col, move, answer, currentDir;
    private static Pos curPos;
    private static int[] dirX = { 0, 1, 0, -1};
    private static int[] dirY = { 1, 0, -1, 0};
    private static int[][] dice = {
            {0, 2, 0},
            {4, 1, 3},
            {0, 5, 0},
            {0, 6, 0}
    };
    private static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        move = Integer.parseInt(st.nextToken());
        answer = currentDir = 0;

        map = new int[row][col];
        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        curPos = new Pos(0,0 );
        for (int i = 0; i < move; i++) {
            firstMove();
        }
        System.out.println(answer);
    }

    private static void firstMove() {
        int nextX = curPos.x + dirX[currentDir];
        int nextY = curPos.y + dirY[currentDir];

        if (!isValid(nextX, nextY)) {
            nextX = curPos.x + dirX[(currentDir + 2) % 4];
            nextY = curPos.y + dirY[(currentDir + 2) % 4];
            currentDir = (currentDir + 2) % 4;
        }

        curPos = new Pos(nextX, nextY);
        getScore(nextX, nextY);
        findNextDir(nextX, nextY);
    }

    private static void findNextDir(int x, int y) {
        // 현재 주사위 아랫면 구하기
        switch (currentDir) {
            case 0 :
                int temp = dice[1][2];
                dice[1][2] = dice[1][1];
                dice[1][1] = dice[1][0];
                dice[1][0] = dice[3][1];
                dice[3][1] = temp;
                break;
            case 1 :
                temp = dice[3][1];
                dice[3][1] = dice[2][1];
                dice[2][1] = dice[1][1];
                dice[1][1] = dice[0][1];
                dice[0][1] = temp;
                break;
            case 2 :
                temp = dice[1][0];
                dice[1][0] = dice[1][1];
                dice[1][1] = dice[1][2];
                dice[1][2] = dice[3][1];
                dice[3][1] = temp;
                break;
            case 3 :
                temp = dice[0][1];
                dice[0][1] = dice[1][1];
                dice[1][1] = dice[2][1];
                dice[2][1] = dice[3][1];
                dice[3][1] = temp;
                break;
        }

        int a = dice[3][1];
        if (a > map[x][y]) {
            currentDir = (currentDir + 1) % 4;
        } else if (a < map[x][y]) {
            currentDir = (currentDir + 3) % 4;
        }
    }

    private static void getScore(int x, int y) {
        int score = map[x][y];
        int len = findLen(x, y, score);
        answer += score * len;
    }

    private static int findLen(int x, int y, int score) {
        boolean[][] temp = new boolean[row][col];
        int len = 0;
        Queue<Pos> queue = new LinkedList<>();
        queue.add(new Pos(x, y));
        temp[x][y] = true;

        while (!queue.isEmpty()) {
            Pos pop = queue.poll();
            len++;
            for (int i = 0; i < 4; i++) {
                int nextX = pop.x + dirX[i];
                int nextY = pop.y + dirY[i];

                if (!isValid(nextX, nextY)) {
                    continue;
                }

                if (map[nextX][nextY] != score) {
                    continue;
                }

                if (temp[nextX][nextY]) {
                    continue;
                }

                queue.add(new Pos(nextX, nextY));
                temp[nextX][nextY] = true;
            }
        }
        return len;
    }

    private static boolean isValid(int x, int y) {
        if (x < 0 || x >= row || y < 0 || y >= col) {
            return false;
        }
        return true;
    }

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