[C++] 백준 23288 삼성기출 주사위 굴리기 2

2021 하반기 삼성 기출이 올라왔다해서 후다닥 풀어봤다

이 문제는 총 55분 가량 걸렸는데 문제를 잘못 읽어서 한 20분 넘게 날려서 아쉬웠다

 

삼성 기출을 쉽게 푸는 법을 설명하기 위해 어떤식으로 접근하였는지 서술해보고자 한다

 

먼저 주사위 모양을 살펴보았다

나는 주석처리된 부분처럼 배열의 인덱스를 정하였다

그 후 주사위가 구를 때 어떤 위치에 어떤 인덱스가 가게 되는지를 살펴보았다

다행히 문제에서 힌트를 주었다

 

먼저 문제에서 준 주사위 초기값

 

 

주사위 배열을 초기값인 2,4,1,3,5,6으로 채워주었다

 

그다음 초기값이 동쪽으로 변할 때 어떻게 변화하는지 살펴보았다

 

 

살펴보면 1,5번 인덱스는 그대로 2번은 3번으로, 3번은 4번으로, 4번은 6번으로, 6번은 2번으로 바뀐 것을 알 수 있다

이런 규칙에 따라서 move dice 함수를 만들어주었다

노가다가 들어가긴 하지만 주사위 문제를 몇 문제 풀어본 결과 나는 이게 가장 빠른 풀이라고 생각한다

동쪽을 알았다면 서쪽은 매우 쉽다

바뀌는 부분만 반대로 만들면 된다

 

다음에는 북,남쪽이 필요하다

 

 

이 주사위가 남쪽으로 이동하면 이렇게 된다고 문제에서 알려주었다

 

 

실제 시험장에서도 알려주었는지는 모르겠지만 이렇게 친절한 문제라니ㅋㅋㅋ

안알려줬으면 머리속에서 주사위 돌리느라 고생깨나 했을 듯 하다

 

아무튼 이 그림을 보면 남쪽으로 바뀔때는 2,4가 그대로 1은 3으로, 3은 5로, 5는 6으로, 6은 1로 간다

이러한 규칙에 따라 move dice 함수를 먼저 만들어주었다

 

그 다음은 주사위 이동을 실제로 시켜보았다

 

next 위치를 한 번 만들어 보고 그 위치가 범위를 벗어난다면 방향에 2를 더해 (반대방향) 다시 이동시켜주었다

그 과정에서 k의 증가가 일어나면 안되니까 한 번 감소시켜주었다

 

그 다음은 해당 위치에서 얻을 수 있는 점수를 계산해야한다

나는 여기서 실수 했다

실제로 주사위가 A,B에 따른 방향을 포함하여 이동하는 거리를 계산하는 줄 알았는데 주사위의 이동과 별개로 그냥 갈 수 있는 거리였다

쉬운 문제를 너무 어렵게 생각했던 것 같다

print dice는 이 때 만든 함수인데 주사위를 잘못 이동시켰나..?싶어서 만들었다

후에 여러 테스트케이스를 검증할때도 사용하였으니 하나 만들어두면 좋을 듯 하다

 

아무튼 해당 위치에서 dfs를 이용해 이동할 수 있는 위치의 개수를 세어 주었고 그 개수를 B와 곱하여 점수를 계산했다

이러한 이동을 K번 반복하면 문제 끝!

주사위의 이동 구현 + dfs,bfs로 연속해서 이동할 수 있는 거리 구하기가 핵심인 것 같았던 문제

 

 

#include <stdio.h>
 
int dice[7] = {0,2,4,1,3,5,6}; 
int dice_tmp[7];
int grid[21][21];
int visit[21][21];
 
//   1
// 2 3 4
//   5
//   6
 
int dc[4] = {0,1,0,-1};
int dr[4] = {-1,0,1,0};
int N,M,K;
 
void print_dice(){
    printf("  %d  \n",dice[1]);
    printf("%d %d %d\n",dice[2],dice[3],dice[4]);
    printf("  %d  \n",dice[5]);
    printf("  %d  \n",dice[6]);
    printf("\n");
}
 
void move_dice(int dir){
    if(dir==0){ // 북
        dice_tmp[6] = dice[1];
        dice_tmp[2] = dice[2];
        dice_tmp[1] = dice[3];
        dice_tmp[4] = dice[4];
        dice_tmp[3] = dice[5];
        dice_tmp[5] = dice[6];
    }
    else if(dir==1){ // 동
        dice_tmp[1] = dice[1];
        dice_tmp[3] = dice[2];
        dice_tmp[4] = dice[3];
        dice_tmp[6] = dice[4];
        dice_tmp[5] = dice[5];
        dice_tmp[2] = dice[6];
    }
    else if(dir==2){ // 남
        dice_tmp[3] = dice[1];
        dice_tmp[2] = dice[2];
        dice_tmp[5] = dice[3];
        dice_tmp[4] = dice[4];
        dice_tmp[6] = dice[5];
        dice_tmp[1] = dice[6];
    }
    else{ // 서
        dice_tmp[1] = dice[1];
        dice_tmp[6] = dice[2];
        dice_tmp[2] = dice[3];
        dice_tmp[3] = dice[4];
        dice_tmp[5] = dice[5];
        dice_tmp[4] = dice[6];
    }
    for(int i = 1 ; i <= 6 ; i++)
        dice[i] = dice_tmp[i];
}
 
void visit_init(){
    for(int i = 1 ; i <= 20 ; i++){
        for(int j = 1; j <= 20 ; j++)
            visit[i][j] = 0;
    }
}
 
void count_move(int r, int c, int B, int dist){
    if(visit[r][c]) return;
    visit[r][c] = 1;
    for(int i = 0 ; i < 4 ; i++){
        int next_r = r + dr[i];
        int next_c = c + dc[i];
        if(next_r<=0 || next_c<=0 || next_r > N || next_c > M) continue;
        if(grid[next_r][next_c]==B) count_move(next_r,next_c,B,dist+1);
    }
}
 
int count_visit(){
    int res = 0;
    for(int i = 1 ; i <= 20 ; i++){
        for(int j = 1; j <= 20 ; j++)
            if(visit[i][j]) res++;
    }
    return res;
}
 
int main(){
    scanf("%d %d %d",&N,&M,&K);
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= M ; j++)
            scanf("%d",&grid[i][j]);
    }
 
    int r = 1, c = 1, dir = 1, score = 0,b,k=1;
    bool isFirst = true;
    for(int k = 1 ; k <= K ; k++){
        int next_r = r+dr[dir];
        int next_c = c+dc[dir];
 
        // 주사위가 이동 방향으로 한 칸 굴러간다. 만약, 이동 방향에 칸이 없다면, 이동 방향을 반대로 한 다음 한 칸 굴러간다.
        if(next_r<=0 || next_c<=0 || next_r > N || next_c > M){
            dir = (dir+2)%4; // 반대방향
            k--;
            continue;
        }
 
        // 주사위 배열 바꾸기
        move_dice(dir);
        //print_dice();
 
        // 주사위의 아랫면에 있는 정수 A와 주사위가 있는 칸 (x, y)에 있는 정수 B를 비교해 이동 방향을 결정한다.
        int A = dice[6];
        int B = grid[next_r][next_c];
 
        if(A>B) dir = (dir+1)%4;
        else if(A<B) dir = (dir+3)%4;
 
        visit_init();
        count_move(next_r,next_c,B,0);
        int C = count_visit();
        
        score += B*C;
        r = next_r; c = next_c;
    }
    printf("%d\n",score);
}