[백준/C++] 23288 - 주사위 굴리기 2

풀이 시간: 2h20m20s95

시간 복잡도: O(KNM)

공간 복잡도: O(NM)

문제

입력

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

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

출력

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

문제 풀이

주사위를 굴릴 때마다 전개도를 어떻게 저장할 것인가?

현재 이동 방향을 따로 저장해준 후, 위 전개도대로 각 위치를 변경해주면 된다.

따라서 나는 이동 방향과 주사위 각 방향에 대한 값을 따로 저장해두기로 했다.

 

우선 동남서북 순서대로 0, 1, 2, 3번이라는 순서 정수값을 매겨 이동 방향(move)을 결정하도록 했다.

상하의 경우에는 각각 4, 5번째에 해당한다.

int move = 0; // 처음 시작 이동 방향은 동쪽(0번째)
int dice[6] = { 3, 5, 4, 2, 1, 6 }; // 처음 주사위 위치의 값 (순서대로 동남서북상하)

 

동남서북이 순서대로 0, 1, 2, 3번이라는 것을 이용하여, 주사위 90도 시계/반시계 방향으로 회전하는 부분은 다음과 같이 구현했다.

if (A > B) move = (move + 1) % 4; // 90도 시계 방향 회전
else if (A < B) move = (move + 3) % 4; // 90도 반시계 방향 회전

 

가장 메인이 되는 부분은 점수를 획득하는 부분인데, 이 부분에 있어서 bfs 알고리즘을 사용하여 동서남북을 전부 탐색하면서 다음 위치의 값이 현재 위치의 값과 같은 값일 경우에만 연속으로 이동할 수 있는 칸의 수(C)를 하나 추가해주도록 하였다.

오류 수정

초기 코드에서는 예제 1~7까지는 정답이 잘 나왔는데, 예제 8번에서만 계속 다른 값이 나왔다.

예제 8번 출력이 계속 3690이 나온다.

 

질문 게시판을 보니 주사위 전개도를 제대로 설정하지 않았을 경우에도 예제 7번까지는 맞다고 나와있다.

https://www.acmicpc.net/board/view/134000

글 읽기 - 마지막 테스트케이스만 틀리시는 분들 보세요

그래서 다시 주사위 전개도를 살펴보았다.

틀린 건 없다고 생각했는데, 다시 보니 남쪽과 북쪽으로 이동하는 방향이 서로 바뀌어있었던 것이다.

전개도를 서로 바꿔주었더니 정답이 잘 나왔다.

전체 코드

#include <iostream>
#include <queue>
using namespace std;
int N, M, K, moveDir = 0, score = 0;
int dice[6] = { 3, 5, 4, 2, 1, 6 }; // 처음 주사위 위치의 값 (순서대로 동남서북상하)
int arr[20][20] = { 0, };
int curR = 0, curC = 0; // 현재 위치 (0, 0)
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 동남서북
pair<int, int> nextPos; // 다음 위치

pair<int, int> movePos(int r, int c) { // 현재 위치 이동
    switch (moveDir) {
        case 0: // 동
            c++;
            break;
        case 1: // 남
            r++;
            break;
        case 2: // 서
            c--;
            break;
        case 3: // 북
            r--;
            break;
    }

    // 이동 방향에 칸이 없을 경우 반대 방향으로 설정
    if (r < 0 || r >= N || c < 0 || c >= M) {
        moveDir = (moveDir + 2) % 4; // 반대 방향
        // 좌표 수정 (이미 위에서 이동한 좌표에 한 칸 더 이동)
        switch (moveDir) {
            case 0: // 동
                c += 2;
                break;
            case 1: // 남
                r += 2;
                break;
            case 2: // 서
                c -= 2;
                break;
            case 3: // 북
                r -= 2;
                break;
        }
    }
    return {r, c};
}

void rollDice() { // 주사위 전개도 변경
    int temp;
    switch (moveDir) {
        case 0: // 동
            temp = dice[0];
            dice[0] = dice[4]; // 동 <- 상
            dice[4] = dice[2]; // 상 <- 서
            dice[2] = dice[5]; // 서 <- 하
            dice[5] = temp; // 하 <- 동
            break;
        case 1: // 남
            temp = dice[1];
            dice[1] = dice[4]; // 남 <- 상
            dice[4] = dice[3]; // 상 <- 북
            dice[3] = dice[5]; // 북 <- 하
            dice[5] = temp; // 하 <- 남
            break;
        case 2: // 서
            temp = dice[2];
            dice[2] = dice[4]; // 서 <- 상
            dice[4] = dice[0]; // 상 <- 동
            dice[0] = dice[5]; // 동 <- 하
            dice[5] = temp; // 하 <- 서
            break;
        case 3: // 북
            temp = dice[3];
            dice[3] = dice[4]; // 북 <- 상
            dice[4] = dice[1]; // 상 <- 남
            dice[1] = dice[5]; // 남 <- 하
            dice[5] = temp; // 하 <- 북
            break;
    }
}

void getScore() { // 점수 획득
    int B = arr[curR][curC]; // 주사위가 있는 칸의 정수
    int C = 1; // 이동할 수 있는 칸의 수
    bool visited[20][20] = { false, };
    queue<pair<int, int>> q;
    q.push({curR, curC}); // 현재 위치
    visited[curR][curC] = true;

    while (!q.empty()) {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nX = curX + dir[i][0];
            int nY = curY + dir[i][1];
            if (nX < 0 || nX >= N || nY < 0 || nY >= M || visited[nX][nY]) continue;
            if (B == arr[nX][nY]) {
                visited[nX][nY] = true;
                q.push({nX, nY});
                C++;
            }
        }
    }
    score += B * C;
}

void changeDir() { // 이동 방향 결정
    int A = dice[5]; // 주사위 아랫면 정수
    int B = arr[curR][curC]; // 주사위가 있는 칸의 정수
    if (A > B) moveDir = (moveDir + 1) % 4; // 90도 시계 방향 회전
    else if (A < B) moveDir = (moveDir + 3) % 4; // 90도 반시계 방향 회전
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> arr[i][j];
    while (K--) { // 이동 횟수
        nextPos = movePos(curR, curC);
        curR = nextPos.first;
        curC = nextPos.second;
        rollDice();
        getScore();
        changeDir();
    }
    cout << score;
    return 0;
}

 

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

23288번: 주사위 굴리기 2