백준 23288 주사위 굴리기 2 (C++)

문제 링크

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

23288번: 주사위 굴리기 2

 

문제 풀이

주사위의 이동은 주사위 굴리기 1 처럼 구현했다. 그럼에도 불구하고 주사위 굴리는 부분 구현 실수한 것을 계속 발견하지 못했던 문제이다. 그것도 모르고 엉뚱한 곳에서 삽질했던 문제.. 아니 주사위 굴리기 1은 잘 풀어놓고 왜...?

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int dice[7] = { 0, 1, 2, 3, 4, 5, 6 };
int dice2[7] = { 0, 1, 2, 3, 4, 5, 6 };
int dx[] = { 0, -1, 0, 1 };
int dy[] = { 1, 0, -1, 0 }; //반시계 방향 순

int bfs(vector<vector<int>>& a, int x, int y, int num) {
    //x, y에서 연속해서 이동할 수 있는 칸의 수, num과 같은 곳으로 이동
    int n = a.size();
    int m = a[0].size();

    vector<vector<bool>> d(n, vector<bool>(m, false));
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    d[x][y] = true;

    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (a[nx][ny] == num && d[nx][ny] == false) {
                    d[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }

    int cnt = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (d[i][j]) {
                cnt += 1;
            }
        }
    }
   
    return cnt; //x, y칸에서 연속해서 이동할 수 있는 칸의 수 C
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    int x = 0;
    int y = 0; //주사위의 아랫면이 있는 지도에서의 위치
    int dir = 0; //주사위의 시작 방향

    int ans = 0; //각 이동에서 획득하는 점수의 합
    while (k--) { //주사위가 k번 이동
        //주사위가 이동 방향으로 한 칸 굴러감
        int nx = x + dx[dir];
        int ny = y + dy[dir];
       
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) { //이동방향에 칸이 없다면 이동방향 반대로 한 다음 한 칸 이동
            dir = (dir + 2) % 4;
            nx = x + dx[dir];
            ny = y + dy[dir];

        }

        // 도착한 칸(x, y)에 대한 점수 획득
        int cnt = bfs(a, nx, ny, a[nx][ny]); //현재 칸에 있는 정수와 연속해서 갈 수 있는 칸의 개수
        ans += (cnt * a[nx][ny]);

        //주사위의 밑면
        if (dir == 0) { //동쪽
            int temp = dice[6];
            dice[6] = dice[3];
            dice[3] = dice[1];
            dice[1] = dice[4];
            dice[4] = temp;
        }
        else if (dir == 1) { //북쪽
            int temp = dice[1];
            dice[1] = dice[5];
            dice[5] = dice[6];
            dice[6] = dice[2];
            dice[2] = temp;
        }
        else if (dir == 2) { //서쪽
            int temp = dice[4];
            dice[4] = dice[1];
            dice[1] = dice[3];
            dice[3] = dice[6];
            dice[6] = temp;
        }
        else if (dir == 3) { //남쪽
            int temp = dice[2];
            dice[2] = dice[6];
            dice[6] = dice[5];
            dice[5] = dice[1];
            dice[1] = temp;
        }

        // 주사위의 이동방향 결정
        if (dice[6] > a[nx][ny]) { //주사위의 아랫면에 있는 정수 A > 칸에 있는 정수 B -> 90도 시계방향
            dir = (dir + 3) % 4;
        }
        else if (dice[6] < a[nx][ny]) { // -> 90도 반시계 방향
            dir = (dir + 1) % 4;
        }
        x = nx;
        y = ny;
 
    }

    cout << ans << '\n';

    return 0;
}