[BOJ] 23288 : 주사위 굴리기

문제 링크

23288번: 주사위 굴리기 2 (acmicpc.net)

23288번: 주사위 굴리기 2

지도위에 놓인 주사위를 굴리며 점수를 획득하는 게임.

풀이

N x M 크기의 지도에 (1,1) 좌표에 주사위가 놓여져있다.

  2
4 1 3
  5
  6

주사위의 초기 상태 전개도는 위와 같다. 윗면이 1이고, 아랫면이 6 오른쪽면이 3이다.

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

주사위는 다음과 같은 규칙으로 이동하고 점수를 획득한다.

먼저 우리가 가지고 있어야 할 정보는 어떤 것들이 있을지 생각해보자.

 1. 지도

지도의 각 칸이 어떤 숫자가 있는지 알아야한다. Map[20][20] 의 int 배열을 만들어주었고 값은 입력으로 주어진다.

 2. 주사위의 상태

현재 주사위 전개도의 상태를 저장하고 있어야한다.

나는 dice[6] 라는 1차원 배열을 만들어서 주사위의 전개도를 표현했다.

0부터 5번 인덱스까지 순서대로 위, 뒤, 오, 왼, 앞, 아래 순서대로 지정했다.

그리고 주어진 값에 따라 순서대로 1, 2, 3, 4, 5, 6 으로 초기값을 넣어줬다.

사실, 순서는 각자 정하기 나름이다.

 3. 방향

방향도 사실 순서 상관없이 동서남북만 표현하기만 하면 된다.

하지만 주사위의 이동 방향이 90도로 시계 또는 반시계방향으로 회전하는 경우가 있다.

그렇기 때문에 dy[], dx[] 배열을 만들 때, 동->남->서->북 순서대로 방향을 정하면 방향 인덱스를 하나를 더하거나 빼서 시계 또는 반시계 방향으로 회전시키기 쉽다.

 

일단 기본적으로 필요한 정보는 이 정도가 될 것 같다.

• 주사위 방향 전환

1번 과정이나 3번 과정에서 주사위의 방향이 전환된다.

1번에서 주사위가 범위를 벗어나게 되면 방향이 반대로 바뀌게 되는데

 나는 0번 = 동, 1번 = 남, 2번 = 서, 3번 = 북 으로 정해두었기 때문에 서로 반대방향인 동,서와 남,북은 번호상 2개가 차이나는 것을 알 수 있다. 그렇기 때문에 방향을 반대로 바꾸기 위해서는 현재 방향에 + 2를 해준다음에 3을 넘어가는 경우는 모듈러를 이용해서 %4 해주면 된다.

또 3번 과정에서는 시계 또는 반시계 방향으로 회전하는 경우가 있다.

시계 방향으로 회전할 때는 방향 인덱스를 + 1 해주고, 반시계 방향으로 회전할 때는 방향 인덱스를 - 1 해주면 된다.

이때 역시 방향 인덱스가 범위 0~3을 벗어나는 경우에는 값을 조정해준다.

이것이 내가 방향을 동남서북 순으로 정해준 이유이다. 

• 점수 획득

점수는 현재 주사위가 있는 칸의 숫자인 B와 주사위가 현재 칸과 같은 숫자만 밟으면서 이동할 수 있는 최대 칸 수인 C를 곱한 만큼 점수를 획득하게 된다.

B 값은 입력으로 주어진 정보이므로 바로 구할 수 있는데, C는 BFS를 이용해서 직접 구해줘야한다.

주사위가 상하좌우 인접한 칸 중에 같은 숫자가 있는 칸으로만 이동해서 최대 몇 칸을 이동할 수 있는 지 구해주면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 20 + 5;
int N, M, K;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int Map[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int dice[6]; // 위, 뒤, 우, 좌, 앞, 아래
int Score;
void Input();
void Solve();
bool is_ok(pair<int, int>);
void get_score(pair<int, int>);
void roll_dice(int);
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    Input();
    Solve();
    cout << Score << "\n";
    return 0;
}
 
void Input() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> Map[i][j];
 
    for (int i = 0; i < 6; i++)
        dice[i] = i + 1;
}
 
// 0, 1, 2, 3 순서대로 동남서북
void Solve() {
    int direction = 0;
    pair<int, int> now = { 1,1 };
    for (int i = 1; i <= K; i++){
        pair<int, int> next = { now.first + dy[direction], now.second + dx[direction] };
        if (!is_ok(next)) {
            direction += 2;
            direction %= 4;
        }
        roll_dice(direction);
        next = { now.first + dy[direction], now.second + dx[direction] };
        now = next;
        get_score(now);
        int A = dice[5];
        int B = Map[now.first][now.second];
        if (A > B)
            direction ++;
        else if (A < B)
            direction += 3;
        direction %= 4;
    }
}
 
bool is_ok(pair<int, int> next) {
    if (next.first < 1 || next.first> N || next.second < 1 || next.second > M)
        return false;
    return true;
}
 
void get_score(pair<int, int> now) {
    int B = Map[now.first][now.second];
    queue<pair<int, int>> q;
    q.push(now);
    memset(visited, false, sizeof(visited));
    int C = 0;
    while (!q.empty()) {
        pair<int, int> position = q.front();
        q.pop();
        if (visited[position.first][position.second])
            continue;
        C++;
        visited[position.first][position.second] = true;
        for (int i = 0; i < 4; i++) {
            pair<int, int> next = { position.first + dy[i], position.second + dx[i] };
            if (is_ok(next) && Map[next.first][next.second] == B)
                q.push(next);
        }
    }
    Score += B * C;
}
 
void roll_dice(int direction) {
    // 위, 뒤, 오, 왼, 앞, 아래
    int temp[6];
    for (int i = 0; i < 6; i++)
        temp[i] = dice[i];
    if (direction == 0) {
        //동쪽으로 굴러감
        dice[0] = temp[3];
        dice[2] = temp[0];
        dice[3] = temp[5];
        dice[5] = temp[2];
    }
    else if (direction == 1) {
        //남쪽으로 구름
        dice[0] = temp[1];
        dice[4] = temp[0];
        dice[5] = temp[4];
        dice[1] = temp[5];
    }
    else if (direction == 2) {
        //서쪽으로 구름
        dice[0] = temp[2];
        dice[3] = temp[0];
        dice[5] = temp[3];
        dice[2] = temp[5];
    }
    else if (direction == 3) {
        //북쪽으로 구름
        dice[0] = temp[4];
        dice[1] = temp[0];
        dice[5] = temp[1];
        dice[4] = temp[5];
     }
}

앞서 풀었던 상어 문제들에 비하면 그렇게 구현이 복잡하지는 않은 것 같다.