boj, 백준) 23288. 주사위 굴리기2 (C/C++)

1. 문제 링크

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

23288번: 주사위 굴리기 2

2. 문제 개요

크기가 N*M인 지도가 존재.

지도의 오른쪽은 동쪽, 위쪽은 북쪽..

지도의 좌표는 (r,c)로 나타내고 가장 왼쪽 위 (1,1), 가장 오른쪽 밑은(n, m).

전개도

주사위의 전개도는 위와 같다.

 

그리고 주사위를 굴릴 때 특정한 규칙이 있고 점수를 매길 때도 특정한 규칙이 있다.

 

 

3. 문제 힌트

이러한 부류의 문제는

 

1. 주사위를 어떻게든 굴린다.

2. 점수를 매긴다.

 

이렇게 나눌 수 있다. 점수를 매길 때, 규칙이 상당히 복잡하기 때문에 처음에 정리를 잘하고 풀지 않으면 코딩하고

외않되 

할 수 있다.. 조심하자..

 

1. 주사위를 굴릴 때를 먼저 살펴보자.

괜히 복잡하게 생각하지 말자. 초기 상태를 기준으로, 동, 서, 남, 북 쪽으로 갈 때 어떻게 상태가 바뀌는지 잘 생각해보자.

 

복잡하게 생각하면.. 이거 굴릴 때마다 방향이 바뀌고.. 방향이 바뀌면 같은 방향으로 돌려도 바닥면의 숫자가 바뀌는 거 아냐..?라고 생각할 수 있다.

 

 

2. 규칙이 상당히 복잡하게 나와있는데 하나, 하나 정리해서 flow chart로 만들어봐도 좋겠다. 이러면 구현을 끝내고 실수를 고치는데 시간을 많이 사용하지 않아도 된다.

 

 

이점을 유의해서 한 번 더 풀어보자!

 

 

4. 문제 풀이

 

주사위를 '상태'로 생각해보자.

 

초기 상태

예를 들어, 위의 초기 상태에서 동쪽으로 움직였을 때의 상태변화이다.

가상으로 주사위를 조립해서 굴리고 다시 위 모양으로 펼친다고 생각해보자

 

초기상태에서 동쪽으로 이동한 상태

초기상태 -> 북쪽으로 이동한 상태

이런 형태로 주사위의 상태를 표현할 수 있겠다.

주사위를 배열로 선언해서 dice[1] = 1 이런 형태로 지정 해놓고, 초기상태에서 북쪽으로 이동한 경우,

dice[1] = 5 --> 기존 1이 있었던 자리에 5가 있다.

이렇게 표현할 수 있겠다.

 

주사위의 움직임은 이렇게 표현할 수 있고,

그다음은 주사위의 좌표, 방향 등을 사용해서 규칙을 적절히 지켜가면서 반복, 문제를 해결할 수 있다.

 

BFS는 간단히(?) 구현할 수 있기 때문에 자세한 풀이는 없고 BFS관련 기본 문제를 풀어본다면 범위를 구하는 것은 간단히 할 수 있을 거라 생각한다.

 

 

5. 코드

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

int map[21][21];
int n, m, k, ret;

int dice[7]={0, 1, 2, 3, 4, 5, 6};
int cur_dir=0;  //E=0, S=1, W=2, N=3
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int cur_y = 1, cur_x = 1;
const int east = 0, south = 1, west = 2, north=3, dice_bottom = 6;


void Rotate_dice()
{
    //moving
    if(cur_dir == east)
    {
        if(cur_x < m)
            cur_x += 1;
        else{
            cur_dir = west;
            cur_x -=1;
        }
    }
    else if(cur_dir == south)
    {
         if(cur_y < n)
            cur_y += 1;
        else{
            cur_dir = north;
            cur_y -=1;
        }
    }
    else if(cur_dir == west)
    {
        if(cur_x > 1)
            cur_x -= 1;
        else{
            cur_dir = east;
            cur_x +=1;
        }   
    }
    else{
        if(cur_y > 1)
            cur_y -= 1;
        else{
            cur_dir = south;
            cur_y +=1;
        }
    }


    //rotating
    if(cur_dir == east)
    {
        int temp = dice[1];
        dice[1] = dice[4];
        dice[4] = dice[6];
        dice[6] = dice[3];
        dice[3] = temp;
        dice[2] = dice[2];
        dice[5] = dice[5];
    }
    else if(cur_dir == south)
    {
        int temp = dice[1];
        dice[1] = dice[2];
        dice[2] = dice[6];
        dice[6] = dice[5];
        dice[5] = temp;
        dice[4] = dice[4];
        dice[3] = dice[3];

       
    }
    else if(cur_dir == west)
    {
        int temp = dice[1];
        dice[1] = dice[3];
        dice[3] = dice[6];
        dice[6] = dice[4];
        dice[4] = temp;
        dice[2] = dice[2];
        dice[5] = dice[5];
    }
    else
    {
        int temp = dice[1];
        dice[1] = dice[5];
        dice[5] = dice[6];
        dice[6] = dice[2];
        dice[2] = temp;
        dice[4] = dice[4];
        dice[3] = dice[3];
    }
    return;
}

int bfs()
{
    bool visited[21][21] = {false,};

    queue<pair<int,int>> q;
    q.push({cur_y,cur_x});
    visited[cur_y][cur_x] = true;
    int cnt = 0;

    while(!q.empty())
    {
        pair<int,int> cur = q.front();
        ++cnt;
        q.pop();

        for(int dir = 0; dir < 4; ++dir)
        {
            pair<int,int> next;
            next.first = cur.first + dy[dir];
            next.second = cur.second + dx[dir];

            if(next.first < 1 || next.second <1 || next.first > n ||next.second > m || visited[next.first][next.second])
                continue;
            
            if(map[next.first][next.second] != map[cur_y][cur_x])
                continue;


            visited[next.first][next.second] = true;
            q.push(next);
            
        }

    }

    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> k;

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            cin >> map[i][j];

    while(k--)
    {
        Rotate_dice();

        int num = bfs();
        ret += num*map[cur_y][cur_x];

        if(map[cur_y][cur_x] < dice[dice_bottom])
        {
            cur_dir += 1;
            cur_dir %= 4;
        }
        else if(map[cur_y][cur_x] > dice[dice_bottom])
        {
            cur_dir += 3; //(4-1)
            cur_dir %= 4;
        }
        else{
            // nothing to do
        }

    }


    cout << ret << '\n';
    
    return 0;
}

 

 

6. 결과