ksh021144

ksh021144

Learn more, Do more.

백준 23288 - 주사위 굴리기 2

3 분 소요

백준 23288 문제 바로가기

풀이

크기가 $N \times M$인 지도가 존재한다. 지도의 좌표는 (r, c)로 나타내며 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다.

그리고 1~6 숫자가 적힌 주사위가 있다. 마주보는 주사위의 면에 적힌 숫자의 합은 7이다. 이 주사위를 이용하여 게임을 $K$번 수행한다.

1→6
2→5
3→4
  1. 주사위가 이동 방향으로 한 칸 굴러간다. 이동하려는 칸이 맵을 벗어난다면 이동 방향을 반대로 한 다음 한 칸 굴러간다.
  2. 주사위가 도착한 칸 (r, c)에 대한 점수를 획득한다.
  3. 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (r, c)에 있는 정수 B를 비교해 이동 방향을 결정한다.
    • $A>B$인 경우 이동 방향을 90도 시계 방향으로 회전시킨다.
    • $A<B$인 경우 이동 방향을 90도 반시계 방향으로 회전시킨다.
    • $A=B$인 경우 이동 방향에 변화는 없다.

칸 (r, c)에 대한 점수를 구하기 위해서는 지도에 적힌 수(B)를 기준으로 동서남북 인접한 위치에 B가 몇 개 있는지 구해야 한다. 이 부분을 구하기 위해서는 그래프 탐색을 활용하여 인접한 위치가 B인지 확인하면서 개수를 구하면 된다.

핵심이 되는 부분은 주사위의 상태를 변화시키고 저장하는 부분이다.

이것은 초기 주사위 상태를 나타내는 dice 배열과 주사위가 이동했을 때 dice의 인덱스를 활용하기 위한 transition_map 배열을 활용하여 구할 수 있다.

const int transition_map[4][6] = { // 초기 상태의 주사위가 동서남북으로 이동했을 때 적용받는 인덱스
    { 4,1,0,3,5,2 }, // 초기 상태의 주사위를 북쪽으로 굴렸을 때
    { 2,1,5,3,0,4 }, // 초기 상태의 주사위를 남쪽으로 굴렸을 때
    { 1,5,2,0,4,3 }, // 초기 상태의 주사위를 서쪽으로 굴렸을 때
    { 3,0,2,5,4,1 } // 초기 상태의 주사위를 동쪽으로 굴렸을 때
};
int dice[6] = { 6,4,5,3,2,1 }; // 0번 인덱스 : 바닥면

...생략

// 주사위가 d 방향으로 굴렀을 때, 주사위 상태를 나타내는 dice 배열의 변화
int temp[6];
for (int i = 0; i < 6; ++i) {
    temp[i] = dice[transition_map[d][i]];
}
for (int i = 0; i < 6; ++i) {
    dice[i] = temp[i];
}

소스 코드

#include <iostream>
using namespace std;

// 북남서동
const int dr[] = { -1,1,0,0 };
const int dc[] = { 0,0,-1,1 };

int ans;
int N, M, K;
int field[21][21];

bool visited[21][21];
void initVisited() {
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            visited[r][c] = false;
        }
    }
}

inline static bool isRange(const int& r, const int& c) {
    return 0 <= r && r < N && 0 <= c && c < M;
}

int dfsCnt;
int target;
void dfs(int r, int c) {
    ++dfsCnt;
    visited[r][c] = true;
    for (int d = 0; d != 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (!isRange(nr, nc) || visited[nr][nc] || field[nr][nc] != target) continue;
        dfs(nr, nc);
    }
}


const int transition_map[4][6] = {
    { 4,1,0,3,5,2 }, // 북
    { 2,1,5,3,0,4 }, // 남
    { 1,5,2,0,4,3 }, // 서
    { 3,0,2,5,4,1 } // 동
};
int dice[6] = { 6,4,5,3,2,1 }; // 0번 인덱스 : 바닥면

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> N >> M >> K;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            cin >> field[r][c];
        }
    }

    int r = 0, c = 0;
    int bottom = dice[0];
    int d = 3;
    for (int k = 0; k < K; ++k) {
        r += dr[d];
        c += dc[d];
        if (!isRange(r, c)) {
            //if (d == 0) d = 1;
            //else if (d == 1) d = 0;
            //else if (d == 2) d = 3;
            //else if (d == 3) d = 2;
            r -= dr[d];
            c -= dc[d];
            d ^= 1;
            r += dr[d];
            c += dc[d];
        }

        initVisited();
        dfsCnt = 0;
        target = field[r][c];
        dfs(r, c);
        ans += target * dfsCnt;

        int temp[6];
        for (int i = 0; i < 6; ++i) {
            temp[i] = dice[transition_map[d][i]];
        }
        for (int i = 0; i < 6; ++i) {
            dice[i] = temp[i];
        }

        bottom = dice[0];
        if (bottom > target) {
            // 이동 방향을 90도 시계 방향으로 회전한다.
            // 3 -> 1 // 동
            // 2 -> 0 // 서
            // 1 -> 2 // 남
            // 0 -> 3 // 북
            if (d == 3) d = 1;
            else if (d == 2) d = 0;
            else if (d == 1) d = 2;
            else if (d == 0) d = 3;
        }
        else if (bottom < target) {
            // 이동 방향을 90도 반시계 방향으로 회전한다.
            // 3 -> 0 // 동
            // 2 -> 1 // 서
            // 1 -> 3 // 남
            // 0 -> 2 // 북
            if (d == 3) d = 0;
            else if (d == 2) d = 1;
            else if (d == 1) d = 3;
            else if (d == 0) d = 2;
        }
        else {
            continue;
        }
    }
    cout << ans;
    return 0;
}

참고