[BOJ] 23288번 : 주사위 굴리기 2

주사위 굴리기 2 성공

 

접근:

• 주사위 굴리는 방법
  • 주사위를 벡터 형태로 저장하고, 각 인덱스에 들어가는 값은 아래와 같이 정의함
  • 아래 사진 기준으로 동,남,서,북(시계방향)으로 주사위가 회전하면 각 위치에 맞게 숫자 치환해줌

초기 값

초기 값 기준 변경 값 ( 동, 남, 서, 북)

 

• 동서남북 방향으로 연속해서 이동할 수 있는 칸의 수 구하기
  • bfs로 미리 map에 연속하여 이동할 수 있는 칸들을 찾고, 이 점수를 따로 배열에 저장하여 주사위를 굴릴 때 사용

 

 

/*
23288번: 주사위 굴리기 2
https://www.acmicpc.net/problem/23288
*/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define sync_off                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

vector<vector<int>> vec;
int n, m;
int k;

void diceInitialize(vector<int> &dice)
{
    dice[0]=2;
    dice[1]=4;
    dice[2]=1;
    dice[3]=3;
    dice[4]=5;
    dice[5]=6;
}

// map에서 같은 score가 인접해 있으면 점수를 합산해야 함. num * 인접한 갯수
void scoreListInitialize(vector<vector<int>> &scoreList)
{
    int dy[4] = {0, 1, 0, -1};
    int dx[4] = {1, 0, -1, 0};

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (scoreList[i][j] != -1)
                continue;

            queue<pair<int,int>> que;
            que.push({i,j});

            queue<pair<int, int>> sameList;
            sameList.push({i, j});
            scoreList[i][j] = 0;

            while(!que.empty())
            {
                int cy = que.front().first;
                int cx = que.front().second;
                que.pop();

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

                    if (ny < 0 || ny >= n || nx < 0 || nx >= m)
                        continue;;

                    if (scoreList[ny][nx] != -1)
                        continue;

                    if (vec[cy][cx] != vec[ny][nx])
                        continue;

                    sameList.push({ny, nx});
                    scoreList[ny][nx] = 0;

                    que.push({ny, nx});
                }
            }

            int sameCnt = sameList.size();
            int toScore = sameCnt * vec[i][j];

            while (!sameList.empty())
            {
                int cy = sameList.front().first;
                int cx = sameList.front().second;
                sameList.pop();

                scoreList[cy][cx] = toScore;
            }
        }
    }
}

void solve(int &score)
{
    // 상판 : 2번 / 하판 : 5번
    vector<int> dice(6);
    diceInitialize(dice);

    vector<vector<int>> scoreList(n, vector<int>(m, -1));
    scoreListInitialize(scoreList);

    // 동, 남, 서, 북
    int dy[4] = {0, 1, 0, -1};
    int dx[4] = {1, 0, -1, 0};

    int y, x;
    y = x = 0;

    int d = 0;

    while(k--)
    {
        int ny = y + dy[d];
        int nx = x + dx[d];
        // cout << ny << " " << nx << "\n";

        // 만약 주사위가 map을 넘어간다면 반대 방향으로 이동
        if(ny < 0 || ny >= n || nx < 0 || nx >= m)
        {
            d = (d + 2) % 4;
            ny = y + dy[d];
            nx = x + dx[d];
            // 이후 예외처리는 딱히 안하겠음
        }

        y = ny;
        x = nx;

        score += scoreList[y][x];

        // 회전한 방향으로 주사위 변화
        vector<int> temp = dice;
        switch (d)
        {
        case 0:
            // 동
            temp[1] = dice[5];
            temp[2] = dice[1];
            temp[3] = dice[2];
            temp[5] = dice[3];
            break;
        case 1:
            // 남
            temp[0] = dice[5];
            temp[2] = dice[0];
            temp[4] = dice[2];
            temp[5] = dice[4];
            break;
        case 2:
            // 서
            temp[1] = dice[2];
            temp[2] = dice[3];
            temp[3] = dice[5];
            temp[5] = dice[1];
            break;
        case 3:
            // 북
            temp[0] = dice[2];
            temp[2] = dice[4];
            temp[4] = dice[5];
            temp[5] = dice[0];
            break;
        }
        dice = temp;

        // A > B인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
        if (dice[5] > vec[y][x])
        {
            d = (d + 1) % 4;
        }
        // A < B인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
        else if (dice[5] < vec[y][x])
        {
            d = (d + 3) % 4;
        }
        // A = B인 경우 이동 방향에 변화는 없다.
        else
        {
            // nothing to do
        }
    }
}

int main()
{
    sync_off;

    cin >> n >> m >> k;
    vec.resize(n);
    for (int i = 0; i < n; i++)
    {
        vec[i].resize(m);
        for (int j = 0; j < m; j++)
        {
            cin >> vec[i][j];
        }
    }

    int score = 0;  
    solve(score);

    cout<<score;

    return 0;
}