코드트리 Implement 정육면체 한번 더 굴리기 - GOLD3

정육면체 한번 더 굴리기 문제는 골드 3정도의 수준인 문제이다. 

간단하게 문제에 대해 설명하면 

N*N 보드판이 존재하며 각각의 보드판에는 점수가 부여되어 있다. 이제 주사위를 굴리면서 주사위가 위치한 보드판에 있는 점수들을 특정 방법을 통해 합산하고 다음 주사위의 방향을 결정하고 방향에 맞게 다시 주사위를 굴리는 방식으로 m번만큼 반복된 이후에 총 점수를 계싼하는 쉽지 않은 문제이다. 일단 N값이 20정도로 그렇게 높지 않다. 따라서 완전탐색 방법을 이용해서 구현하여도 시간초과가 나지 않는다. 대부분 구현문제는 정말 어려운 문제가 아니라면 완탐을 이용해도 괜찮은 것 같다.

 

일단 문제에서 주어진 조건들에 대해서 잠깐 정리를 하자면 다음과 같다.

• 주사위는 처음 -> 으로 이동한다.
• 주사위가 위치한 보드판위에 있는 점수와 인접한 위치에 같은 점수를 가진 갯수를 총합하여  스코어를 계산한다.
• 주사위의 바닥면과 보드판에 점수를 비교하여 다음 방향을 결정한다.
  • 주사위의 바닥면 > 보드판 점수 : 시계 방향
  • 주사위의 바닥면 < 보드판 점수 : 반시계 방향
  • 주사위의 바닥면 == 보드판 점수 : 진행 방향

#주의 만약 주사위가 이동중 벽을 만난다면 그 반대방향으로 움직여야 한다!!!

예를 들어 제일 처음 1,1에 있던 주사위가 오른쪽으로 이동하면 주사위의 top : 4 bottom : 3이 된다. 이 때 주사위가 위치한 BOARD[1][2]에 값이 3이라면 그 위치부터 상,하,좌,우로 인접한 모든 곳에 3의 값을 가진 갯수를 카운트 한다. 그리고 그 갯수*3 을 점수에 더한다. 이제 bottom과 board의 값을 비교하고, 이 때 bottom : 3 board = 3 둘 다 같으므로 오른쪽 진행방향을 유지한다.

문제 해결

일단 위의 문제는 크게 1. 주사위를 굴리는 로직, 2. 인접한 target 점수 bfs, dfs 탐색, 3. 주사위 이동 방향 결정 으로 나눌 수 있다. 이 3단계 스텝에 맞게 일단 문제를 해결하면 다음과 같ㅊ다.

 

1. 주사위를 굴리는 로직

주사위를 굴리는 로직은 처음 생각할 때는 상당히 오래걸렸지만 아래 백준 문제 해설을 들으며 참고를 했다. 

https://donggoolosori.github.io/2020/11/09/boj-14499/

[백준] 14499번 주사위 굴리기 - C++ - DGOS | 동꿀오소리

일단 기본적인 방법은 다음과 같다

1. 주사위의 6방향을 미리 셋팅 

2. 상,하,좌,우 방향에 맞게 주사위의 위치를 재조정한다.

#-- 주의 : 정육면체 한번 더 굴리기 문제의 경우 벽을 만난경우 반대 방향으로 굴려야 한다. 이 때 -> 방향으로 굴리다가 벽을 만나면 <- 방향으로 굴려줘야 한다. 이 때 반대 방향에 맞게 dir 방향을 재설정 해야한다.

typedef struct dice{
    ll right; ll left; ll top; ll bottom; ll front; ll rear;
}dice;

dice DICE;

void init_dice(){
    // 1번 주사위 setting 
    DICE.top = 1; DICE.front = 2; DICE.right = 3; DICE.left = 4; DICE.rear = 5; DICE.bottom = 6; 
}

void move_right(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll dx = point.second + 1;
    if(!isValidPosition(dx, point.first, sz)){
        move_left(sz); dir =2; return; // 만약에 벽에 박은경우 반대방향으로 움직이면서 방향 재설정
    }
    BOARD[point.first][point.second] = 0;
    BOARD[point.first][dx] = 1;
    dice temp = DICE; DICE.top = temp.left; DICE.bottom = temp.right; DICE.left = temp.bottom; DICE.right = temp.top;
}

void move_left(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll dx = point.second - 1;
    if(!isValidPosition(dx, point.first, sz)){
        move_right(sz); dir = 0; return; // 만약에 벽에 박은경우 반대방향으로 움직이면서 방향 재설정
    }
        
    BOARD[point.first][point.second] = 0;
    BOARD[point.first][dx] = 1;
    dice temp = DICE; DICE.top = temp.right;  DICE.bottom = temp.left; DICE.left = temp.top; DICE.right = temp.bottom;
}

void move_down(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll dy = point.first + 1;
    if(!isValidPosition(point.second, dy, sz)){
        move_up(sz); dir = 3; return; // 만약에 벽에 박은경우 반대방향으로 움직이면서 방향 재설정
    }
    BOARD[point.first][point.second] = 0;
    BOARD[dy][point.second] = 1;

    dice temp = DICE; DICE.top = temp.rear; DICE.bottom = temp.front; DICE.front = temp.top; DICE.rear = temp.bottom;
}

void move_up(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll dy = point.first - 1;
    if(!isValidPosition(point.second, dy, sz)){
        move_down(sz); dir =1; return ; // 만약에 벽에 박은경우 반대방향으로 움직이면서 방향 재설정
    }
    BOARD[point.first][point.second] = 0;
    BOARD[dy][point.second] = 1;

    dice temp = DICE; DICE.top = temp.front; DICE.bottom = temp.rear; DICE.front = temp.bottom; DICE.rear = temp.top;
}

오른쪽과 왼쪽으로 움직일 때는 front 와 rear는 고정이다. 반대로 위쪽과 아래쪽으로 움직이면 left와 right가 고정이다.

포지션체크를 해서 벽을 만난경우 그 반대방향으로 움직여주는 부분을 주의하자

 

2. 인접한 target 점수 확인하는 로직

이 부분은 bfs나 dfs탐색을 하면 되는 문제이기 때문에 해당 방법만 안다면 어렵지 않은 로직이다. 다만 탐색하기전에 항상 visit배열을 초기화하자.

void dfs(ll sz, ll y, ll x, ll target){
    for(ll k=0; k<4; k++){
        ll nx = x + dx[k];
        ll ny = y + dy[k];
        if(isValidPosition(nx, ny, sz) == true && GRID[ny][nx] == target){
            if(VISIT[ny][nx] ==0){
                VISIT[ny][nx] = 1;
                cnt = cnt+1;
                dfs(sz, ny, nx, target);
            }
        }
    }
}


void find_number(ll sz, ll target){
    cnt = 1;
    visit(sz);
    pair<ll, ll>point = get_point(sz);
    dfs(sz, point.first, point.second, target);
}

 

3. 방향을 재설정 하는 로직

이 부분이 아마도 제일 쉬운 로직인것 같다. 문제에서 주어진 조건에 맞게 구현만 해주면된다. 여기서 나머지 연산을 사용하면 값이 넘어갔을 때 다시 돌아올 수 있다.

void set_dir(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll x = point.second; ll y = point.first;
    if(GRID[y][x] < DICE.bottom){ // 주사위 아래가 보드의 값보다 크면 시계 방향으로 회전
        dir = (dir + 1) % 4;
    }
    else if(GRID[y][x] > DICE.bottom){
        dir = (dir - 1 + 4) % 4;
    }
}

 

위 3개의 로직을 반복적으로 돌려주면 해결이 가능하다. 처음 벽을 만났을 때 방향을 바꿔주지 않아서 계속 실패했다. 거의 4시간 넘게 걸린것 같다. 그래도 좋은 데이터를 수집했다.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX_GRID 20

using namespace std;

typedef long long ll;

typedef struct dice{
    ll right; ll left; ll top; ll bottom; ll front; ll rear;
}dice;

ll dx[4] = {0, 0, 1, -1};
ll dy[4] = {1, -1, 0, 0};

dice DICE;
vector<vector<ll> >GRID(MAX_GRID+1, vector<ll>(MAX_GRID+1, 0));
vector<vector<ll> >BOARD(MAX_GRID+1, vector<ll>(MAX_GRID+1, 0));
vector<vector<ll> >VISIT(MAX_GRID+1, vector<ll>(MAX_GRID+1, 0));
ll cnt; ll dir;

void init(ll n){
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=n; j++){
            cin >> GRID[i][j];
        }
    }
    BOARD[1][1] = 1;
    dir = 0;
}

void print(ll n, string str){
    if(str == "GRID"){
        for(ll i=1; i<=n; i++){
            for(ll j=1; j<=n; j++){
                cout << GRID[i][j] << " ";
            }
            cout << "\n";
        }
    }
    else{
        for(ll i=1; i<=n; i++){
            for(ll j=1; j<=n; j++){
                cout << BOARD[i][j] << " ";
            }
            cout << "\n";
        }
    }
}
void init_dice(){
    // 1번 주사위 setting 
    DICE.top = 1; DICE.front = 2; DICE.right = 3; DICE.left = 4; DICE.rear = 5; DICE.bottom = 6; 
}

bool isValidPosition(ll x, ll y, ll sz){
    if(x <=0 || x > sz)
        return false;
    if( y<= 0 || y> sz)
        return false;
    return true;
}
pair<ll, ll>get_point(ll sz){
    ll x = 0; ll y = 0;
    for(ll i=1; i<=sz; i++){
        for(ll j=1; j<=sz; j++){
            if(BOARD[i][j] == 1){
                x = j;
                y = i;
                break;
            }
        }
    }
    return make_pair(y, x);
}
void move_right(ll sz);
void move_left(ll sz);
void move_up(ll sz);
void move_down(ll sz);

void move_right(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll dx = point.second + 1;
    if(!isValidPosition(dx, point.first, sz)){
        move_left(sz); dir =2; return; // 만약에 벽에 박은경우 반대방향으로 움직이면서 방향 재설정
    }
    BOARD[point.first][point.second] = 0;
    BOARD[point.first][dx] = 1;
    dice temp = DICE; DICE.top = temp.left; DICE.bottom = temp.right; DICE.left = temp.bottom; DICE.right = temp.top;
}

void move_left(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll dx = point.second - 1;
    if(!isValidPosition(dx, point.first, sz)){
        move_right(sz); dir = 0; return; // 만약에 벽에 박은경우 반대방향으로 움직이면서 방향 재설정
    }
        
    BOARD[point.first][point.second] = 0;
    BOARD[point.first][dx] = 1;
    dice temp = DICE; DICE.top = temp.right;  DICE.bottom = temp.left; DICE.left = temp.top; DICE.right = temp.bottom;
}

void move_down(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll dy = point.first + 1;
    if(!isValidPosition(point.second, dy, sz)){
        move_up(sz); dir = 3; return; // 만약에 벽에 박은경우 반대방향으로 움직이면서 방향 재설정
    }
    BOARD[point.first][point.second] = 0;
    BOARD[dy][point.second] = 1;

    dice temp = DICE; DICE.top = temp.rear; DICE.bottom = temp.front; DICE.front = temp.top; DICE.rear = temp.bottom;
}

void move_up(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll dy = point.first - 1;
    if(!isValidPosition(point.second, dy, sz)){
        move_down(sz); dir =1; return ; // 만약에 벽에 박은경우 반대방향으로 움직이면서 방향 재설정
    }
    BOARD[point.first][point.second] = 0;
    BOARD[dy][point.second] = 1;

    dice temp = DICE; DICE.top = temp.front; DICE.bottom = temp.rear; DICE.front = temp.bottom; DICE.rear = temp.top;
}
                
void init_visit(ll sz){
    for(ll i=0; i<=sz; i++){
        for(ll j=0; j<=sz; j++){
            VISIT[i][j] = 0;
        }
    }
}

void visit(ll sz){
    init_visit(sz);
    pair<ll, ll>p = get_point(sz);
    VISIT[p.first][p.second] = 1;
}


ll get_number(ll sz){
    pair<ll,ll>point = get_point(sz);
    return GRID[point.first][point.second];
}

void dfs(ll sz, ll y, ll x, ll target){
    for(ll k=0; k<4; k++){
        ll nx = x + dx[k];
        ll ny = y + dy[k];
        if(isValidPosition(nx, ny, sz) == true && GRID[ny][nx] == target){
            if(VISIT[ny][nx] ==0){
                VISIT[ny][nx] = 1;
                cnt = cnt+1;
                dfs(sz, ny, nx, target);
            }
        }
    }
}


void find_number(ll sz, ll target){
    cnt = 1;
    visit(sz);
    pair<ll, ll>point = get_point(sz);
    dfs(sz, point.first, point.second, target);
}

void set_dir(ll sz){
    pair<ll, ll>point = get_point(sz);
    ll x = point.second; ll y = point.first;
    if(GRID[y][x] < DICE.bottom){ // 주사위 아래가 보드의 값보다 크면 시계 방향으로 회전
        dir = (dir + 1) % 4;
    }
    else if(GRID[y][x] > DICE.bottom){
        dir = (dir - 1 + 4) % 4;
    }
    
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n = 0; ll m = 0; ll answer = 0;
    cin >> n >> m;
    init_dice();  init(n);
    // ============= input setting ==============

    
    for(ll i=0; i<m; i++){
        // ==============================  step1. 주사위 이동 ============================== 
        if(dir == 0)
            move_right(n);
        else if(dir == 1)
            move_down(n);
        else if(dir == 2)
            move_left(n);
        else if(dir == 3)
            move_up(n);
        // ============================== step2  ============================== 
        ll number = get_number(n); // 해당 주사위가 위치한 보드에 있는 값 가져오기 
        find_number(n, number);
        answer += (number * cnt); // 그만큼 갯수 추가
        // ============================== step3. 주사위 아랫면과 숫자를 비교해서 이동방향 결정  ============================== 
        set_dir(n); // 방향 결정
    }
    cout << answer << "\n"; 
    return 0;
}