[백준]23288: 주사위 굴리기2(java)

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

23288번: 주사위 굴리기 2

문제

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는 아래와 같다.

  2
4 1 3
  5
  6

주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (1, 1) 이다. 지도의 각 칸에도 정수가 하나씩 있다. 가장 처음에 주사위의 이동 방향은 동쪽이다. 주사위의 이동 한 번은 다음과 같은 방식으로 이루어진다.

1. 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
2. 주사위가 도착한 칸 (x, y)에 대한 점수를 획득한다.
3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
   • A > B인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
   • A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
   • A = B인 경우 이동 방향에 변화는 없다.

칸 (x, y)에 대한 점수는 다음과 같이 구할 수 있다. (x, y)에 있는 정수를 B라고 했을때, (x, y)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 C를 모두 구한다. 이때 이동할 수 있는 칸에는 모두 정수 B가 있어야 한다. 여기서 점수는 B와 C를 곱한 값이다.

보드의 크기와 각 칸에 있는 정수, 주사위의 이동 횟수 K가 주어졌을때, 각 이동에서 획득하는 점수의 합을 구해보자.

이 문제의 예제 1부터 7은 같은 지도에서 이동하는 횟수만 증가시키는 방식으로 구성되어 있다. 예제 8은 같은 지도에서 이동하는 횟수를 매우 크게 만들었다.

입력

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (2 ≤ N, M ≤ 20), 그리고 이동하는 횟수 K (1 ≤ K ≤ 1,000)가 주어진다. 

둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 지도의 각 칸에 쓰여 있는 수는 10 미만의 자연수이다.

출력

첫째 줄에 각 이동에서 획득하는 점수의 합을 출력한다.

예제 입력 1 

4 5 1
4 1 2 3 3
6 1 1 3 3
5 6 1 3 2
5 5 6 5 5

예제 출력 1 

4

가장 처음에 주사위의 이동 방향은 동쪽이다. 따라서, 첫 이동에서 주사위는 (1, 1)에서 (1, 2)로 이동한다. 주사위가 오른쪽으로 한 칸 굴러가고 주사위의 전개도는 다음과 같이 변한다.

  2
6 4 1
  5
  3

(1, 2)에는 1이 있고, (1, 1)에서 동서남북 방향으로 연속해서 이동할 수 있는 칸은 총 4개이다. 따라서, 4점을 획득한다.

4	1	2	3	3
6	1	1	3	3
5	6	1	3	2
5	5	6	5	5

주사위의 아랫면에는 3이 있고, (1, 2)에는 1이 있다. 아랫면에 있는 수가 더 크기 때문에, 이동 방향을 90도 시계 방향으로 회전시켜 남쪽이 된다.

---

풀이

시뮬레이션 + bfs 문제였습니다.

 

다음과 같은 구현을 총 K번 반복합니다.

1) 주사위 굴리기

2) 얻을 수 있는 점수 체크 후 점수 합산

3) 방향 바꾸기

 

1) 주사위 굴리기

주사위는 다음과 같이 배열로 구현하였습니다.

주사위를 굴리면 다음과 같음을 알 수 있습니다.

주사위 굴리는 함수는 아래와 같습니다.

public static void moveDice() {
    int nx = x + dist[d][0];
    int ny = y + dist[d][1];

    //맵 바깥으로 나가면 방향이 반대로 바뀌어야함.
    if(!isIn(nx , ny)) {
        d = (d+2) % 4;
    }

    switch(d) {
        //동쪽
        case 0:
            int tmp = dice[1][2];
            dice[1][2] = dice[1][1];
            dice[1][1] = dice[1][0];
            dice[1][0] = dice[3][1];
            dice[3][1] = tmp;
            break;
        //남쪽
        case 1:
            tmp = dice[3][1];
            for(int i=3; i>=1; i--) dice[i][1] = dice[i-1][1];
            dice[0][1] = tmp;
            break;
        //서쪽
        case 2:
            tmp = dice[1][0];
            dice[1][0] = dice[1][1];
            dice[1][1] = dice[1][2];
            dice[1][2] = dice[3][1];
            dice[3][1] = tmp;
            break;
        //북쪽
        case 3:
            tmp = dice[0][1];
            for(int i=0; i<3; i++) dice[i][1] = dice[i+1][1];
            dice[3][1] = tmp;
            break;
    }

    x += dist[d][0];
    y += dist[d][1];
}

2) 얻을 수 있는 점수 체크 후 점수 합산

현재 말판을 기점으로 인접한 같은 점수는 모두 획득할 수 있습니다.

인접한 같은 점수는 bfs를 통해서 찾아주었습니다.

public static void getScore() {
    Queue<int []> q = new LinkedList<>();
    boolean[][] visited = new boolean[N][M];
    int num = map[x][y];
    int cnt = 1;
    q.add(new int[]{x, y});
    visited[x][y] = true;

    while(!q.isEmpty()) {
        int[] now = q.poll();

        for(int i=0; i<4; i++) {
            int nx = now[0] + dist[i][0];
            int ny = now[1] + dist[i][1];
            //범위 밖 or 이미 방문 or 같은 점수가 아님
            if(!isIn(nx, ny) || visited[nx][ny] || map[nx][ny] != num) continue;
            visited[nx][ny] = true;
            q.add(new int[]{nx, ny});
            cnt++;
        }
    }

    score += cnt * num;
}

 

3) 방향 바꾸기

 

문제에서 주어진 아랫면과 현재 자리의 점수를 비교하여 방향을 바꿔줬습니다.

public static void changeDist() {
    int under = dice[3][1];
    int num = map[x][y];
    if(under > num) {
        d = (d+1) % 4;
    } else if(under < num) {
        d = (d-1);
        if(d<0) d = 3;
    }
}

 

전체 코드

package 백준;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G3_23288_주사위굴리기2 {
    static int N, M, K;
    static int[][] map;
    /*
    0 2 0
    4 1 3
    0 5 0
    0 6 0
     */
    static int[][] dice = {{0, 2, 0}, {4, 1, 3}, {0, 5, 0}, {0, 6, 0}};
    // 동, 남, 서, 북
    static int[][] dist = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    // 초기 방향은 0번 즉, 동쪽이다.
    static int d = 0;
    static int score = 0;
    static int x = 0, y = 0;
    public static void main(String[] args) throws Exception {
        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());
        map = new int[N][M];

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

        while(K-->0) {
            moveDice();
            getScore();
            changeDist();
        }

        System.out.printf("%d", score);
    }

    public static void getScore() {
        Queue<int []> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        int num = map[x][y];
        int cnt = 1;
        q.add(new int[]{x, y});
        visited[x][y] = true;

        while(!q.isEmpty()) {
            int[] now = q.poll();

            for(int i=0; i<4; i++) {
                int nx = now[0] + dist[i][0];
                int ny = now[1] + dist[i][1];
                if(!isIn(nx, ny) || visited[nx][ny] || map[nx][ny] != num) continue;
                visited[nx][ny] = true;
                q.add(new int[]{nx, ny});
                cnt++;
            }
        }

        score += cnt * num;
    }

    public static void moveDice() {
        int nx = x + dist[d][0];
        int ny = y + dist[d][1];

        //맵 바깥으로 나가면 방향이 반대로 바뀌어야함.
        if(!isIn(nx , ny)) {
            d = (d+2) % 4;
        }

        switch(d) {
            //동쪽
            case 0:
                int tmp = dice[1][2];
                dice[1][2] = dice[1][1];
                dice[1][1] = dice[1][0];
                dice[1][0] = dice[3][1];
                dice[3][1] = tmp;
                break;
            //남쪽
            case 1:
                tmp = dice[3][1];
                for(int i=3; i>=1; i--) dice[i][1] = dice[i-1][1];
                dice[0][1] = tmp;
                break;
            //서쪽
            case 2:
                tmp = dice[1][0];
                dice[1][0] = dice[1][1];
                dice[1][1] = dice[1][2];
                dice[1][2] = dice[3][1];
                dice[3][1] = tmp;
                break;
            //북쪽
            case 3:
                tmp = dice[0][1];
                for(int i=0; i<3; i++) dice[i][1] = dice[i+1][1];
                dice[3][1] = tmp;
                break;
        }

        x += dist[d][0];
        y += dist[d][1];
    }

    public static void changeDist() {
        int under = dice[3][1];
        int num = map[x][y];
        if(under > num) {
            d = (d+1) % 4;
        } else if(under < num) {
            d = (d-1);
            if(d<0) d = 3;
        }
    }

    public static boolean isIn(int x, int y) {
        return 0<=x && x<N && 0<=y && y<M;
    }
}