[ BOJ - 23288번 ] 주사위 굴리기 2 (C++)

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

 

[ 풀이 방법 ]

1. 주사위의 다음 이동 방향을 정하는 기능

  - 처음엔 동쪽 방향으로 이동

  - 이후로는 주사위 아랫면의 정수(A)와 보드의 해당 칸의 정수(B)를 비교하여 이동 방향을 결정한다.

      - A > B: 현재 방향에서 90도 시계 방향으로 회전한다.

      - A < B: 현재 방향에서 90도 반시계 방향으로 회전한다.

      - A = B: 현재 방향 그대로, 만약 다음 이동 시 보드 칸을 벗어난다면 이동 방향을 반대로 한다.

      - 주사위 구조체에 다음 이동 방향과 현재 위치를 저장하여 구현한다.

 

2. 주사위 이동 기능

  - 1에서 정한 이동 방향으로 주사위를 한 칸 이동하는 기능

  - 주사위의 위치 이동 + 주사위를 이동 방향으로 굴림

        - 주사위 구조체에 위, 아래, 왼쪽, 오른쪽, 앞, 뒤에 적힌 정수를 저장하고, 이동 방향에 따라 저장된 값을 바꾸어 구현한다.

 

3. 점수 계산 기능

  - DFS를 이용하여 보드의 현재 주사위 위치에 적힌 정수와 같은 값을 가진 인접한 칸을 모두 탐색하여 점수를 계산한다.

  - 점수는 인접한 칸의 개수 x 칸에 저장된 값으로 계산한다.

 

4. 위 기능들을 이동 횟수 K번 만큼 반복하여 총 획득 점수를 구하고 출력하는 기능

 

[ 회고 ]

 주사위 이동 방향이 반대가 되어야 하는 경우를 올바르게 처리하지 못했고 점수 계산 방법에 오류가 있었으며, 주사위를 굴리는 기능을 구현할 때, 각 면에 저장되어야 할 값을 서로 바꾸는 과정에서 순서를 잘 못하여 오류가 발생하였다.

 

 즉, 구현 과정에서 실수가 많았으나 미리 작성해둔 풀이 방법과 충분한 예제 입력을 이용하여 디버깅하고 수정하여 문제를 해결할 수 있었다. 구현 과정 또는 구현을 완료한 시점에 작성해 둔 풀이 방법과 구현 방법이 모두 올바르게 구현되었는지 또는 구현 과정에서 새롭게 생각한 코드에 오류가 있는지 확인하는 과정을 거쳐야 할 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>

#define RIGHT 0
#define DOWN 1
#define LEFT 2
#define UP 3

using namespace std;

int N, M, K;

struct Dice {
  
    int dir, x, y;
    int u, d, l, r, f, b;
    
    Dice() : dir(RIGHT), x(0), y(0), u(1), d(6), l(4), r(3), f(5), b(2) {}
    
    void rotate(int num) {
        if(d > num) dir = (dir+1)%4;
        else if (d < num) dir = (dir+3)%4;
    }
    
    void roll() {
        if(dir == UP) {
            int t = u;
            u = f;
            f = d;
            d = b;
            b = t;
        } else if (dir == DOWN) {
            int t = d;
            d = f;
            f = u;
            u = b;
            b = t;
        } else if (dir == LEFT) {
            int t = l;
            l = u;
            u = r;
            r = d;
            d = t;
        } else if (dir == RIGHT) {
            int t = r;
            r = u;
            u = l;
            l = d;
            d = t;
        }
    }
};

vector<vector<int>> board;

int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {1, 0 ,-1, 0};

int res;

void dfs(int x, int y, vector<vector<bool>>& visited) {
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dirX[i];
        int ny = y + dirY[i];
        
        if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
        if(!visited[nx][ny] && board[nx][ny] == board[x][y]) {
            visited[nx][ny] = true;
            res += board[nx][ny];
            dfs(nx, ny, visited);
        }
        
    }
}

void solve() {
    
    Dice dice;
    
    while (K--) {
        
        int nx = dice.x + dirX[dice.dir];
        int ny = dice.y + dirY[dice.dir];
        if(nx < 0 || nx >= N || ny < 0 || ny >= M) {
            dice.dir = (dice.dir+2)%4;
            nx = dice.x + dirX[dice.dir];
            ny = dice.y + dirY[dice.dir];
        }
        
        
        // 주사위 이동 방향으로 굴림
        dice.roll();
        
        // 주사위 위치 이동
        dice.x = nx;
        dice.y = ny;
        
        // 주사위 다음 이동 방향 결정
        int boardNum = board[nx][ny];
        dice.rotate(boardNum);
        
        // 점수 계산
        vector<vector<bool>> visited(N, vector<bool>(M));
        visited[nx][ny] = true;
        res += board[nx][ny];
        dfs(nx, ny, visited);
        vector<vector<bool>>().swap(visited);
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M >> K;
    board.resize(N, vector<int>(M));
    
    for (int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
    
    solve();
    
    cout << res << '\n';
    
    return 0;
}