[백준] 23288번 주사위 굴리기 2 (C++)

문제)

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

23288번: 주사위 굴리기 2

설명)

시키는데로 순서대로 짜면 괜찮은 문제였다. 

1) 주사위 굴러가기 알고리즘

2) 점수획득 알고리즘: BFS

3) 아랫면 비교, 방향결정 알고리즘

문제가 좀 길어서 자기 자신이 헷갈릴 경우가 많은 것 같은데, define을 사용해서 상수 이름을 결정해 놓으니 괜찮았다.

 

 

코드)

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define U 0
#define D 1
#define E 2
#define W 3
#define S 4
#define N 5


int NN, M, K;
int board[21][21];
int dice[6] = {1,6,3,4,5,2}; //상, 하, 동, 서, 남, 북
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; //남, 동, 북, 서

int reverse(int dir){
    if(dir == 0) return 2;
    if(dir == 1) return 3;
    if(dir == 2) return 0;
    if(dir == 3) return 1;
}

int cycle(int dir){
    if(dir == 0) return 3;
    if(dir == 1) return 0;
    if(dir == 2) return 1;
    if(dir == 3) return 2;
}

int recycle(int dir){
    if(dir == 0) return 1;
    if(dir == 1) return 2;
    if(dir == 2) return 3;
    if(dir == 3) return 0;
}

int u,d,s,w,n,e;

void dice_move(int dir){
    u = dice[U];
    d = dice[D];
    e = dice[E];
    w = dice[W];
    s = dice[S];
    n = dice[N];
    if(dir == 0)//하
    {
        dice[S] = u;//상->남
        dice[D] = s;//남->하
        dice[N] = d;//하->북
        dice[U] = n;//북->상
    }

    if(dir == 1)//우
    {
        dice[E] = u;//상->동
        dice[D] = e;//동->하
        dice[W] = d;//하->서
        dice[U] = w;//서->상
    }
    if(dir == 2)//상
    {
        dice[N] = u;//상->북
        dice[D] = n;//북->하
        dice[S] = d;//하->남
        dice[U] = s;//남->상
    }
    if(dir == 3)//좌
    {
        dice[W] = u;//상->서
        dice[D] = w;//서->하
        dice[E] = d;//하->동
        dice[U] = e;//동->상
    }
}

int BFS(pair<int,int> cur, int val){
    int count=0;
    bool visit[21][21] = {0,};

    queue <pair<int,int>> q;
    visit[cur.X][cur.Y] = 1;
    q.push(cur);
    while(!q.empty()){
        cur = q.front();
        count++;
        q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if (nx < 0 || nx >= NN || ny < 0 || ny >= M) continue;
            if(board[nx][ny] != board[cur.X][cur.Y] || visit[nx][ny]) continue;
            visit[nx][ny] = 1;
            q.push({nx,ny});
        }
    }
    return count;
}

int main(){
    int sum = 0;
    cin>> NN >> M >> K;
    for(int i = 0; i < NN; i++){
        for(int j = 0; j < M; j++){
            cin >> board[i][j];
        }
    }
    int dir = 1;
    pair <int, int> cur;
    cur = {0,0};
    while(K>0){
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        if(nx < 0 || nx >= NN || ny < 0 || ny >= M) { //재배열
            dir = reverse(dir);
            nx = cur.X + dx[dir];
            ny = cur.Y + dy[dir];
        }
        cur = make_pair(nx, ny); //다음칸 이동 1번과정,
        dice_move(dir);

        sum += BFS(cur, dice[D]) * board[cur.X][cur.Y];//점수얻기 과정
        if(dice[D] > board[cur.X][cur.Y]) dir = cycle(dir); //3번과정
        else if(dice[D] < board[cur.X][cur.Y]) dir = recycle(dir);

        K--;
    }
    cout << sum;

}

 

생각지도 못하게.. 삼성 인턴 1차가 되어서... 다음주에 SW역량테스트가 있게되었다...

백준 기출문제를 난이도가 너무 높지않은, 최신순으로 풀기 시작해보고있다!...

화이팅!