[C++] 백준 16928 - 뱀과 사다리 게임

• 문제

• 풀이 과정

• 최종 코드

• 잡담

백준 16928 : 뱀과 사다리 게임
난이도 : 골드 5

시간 : 15분 소요

 

 

 

문제

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

16928번: 뱀과 사다리 게임

 

풀이 과정

 

bfs를 사용하면 쉽게 풀 수 있는 문제이다.

게임판은 1차원배열로 board[101] 로 선언했다. 그 후 주사위의 경우의 수에 따라 bfs를 구현했다.

또한, 주사위 던진 수를 저장하기 위해 pair 자료형을 사용했다.

 

먼저 경우의 수는 +1 부터 +6 까지 총 6가지이다.

현재 칸에서 +1~ +6를 하여 방문하지 않은 칸이면 방문처리를 하고, 큐에 넣는다.

또한, 사다리나 뱀이 있는 칸이라면 해당 칸으로 이동시킨 후 큐에 넣는다.

 

이후 100칸에 도착하면 현재 주사위 횟수를 출력하고, 종료한다.

 

 

최종 코드

#include <iostream>
#include <queue>

using namespace::std;

int N, M;
int board[101];
int visited[101];
queue<pair<int, int>> q;
int di[6] = {1,2,3,4,5,6};

void bfs(int n){
    visited[n] = 1;
    q.push({n, 0});
    
    while(!q.empty()){
        int t = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        if(t == 100){
            printf("%d\n", cnt);
            break;
        }
        
        for(int i=0; i<6; i++){
            int nt = t+di[i];
            if(visited[nt] == 0 && nt<=100){
                if(board[nt] != 0){
                    q.push({board[nt], cnt+1});
                    
                }else{
                    visited[nt] = cnt+1;
                    q.push({nt, cnt+1});
                }
            }
        }
    }
}


int main(){
    scanf("%d %d", &N, &M);
    
    for(int i=0; i<N; i++){
        int t1, t2;
        scanf("%d %d", &t1, &t2);
        board[t1] = t2;
    }
    for(int i=0; i<M; i++){
        int t1, t2;
        scanf("%d %d", &t1, &t2);
        board[t1] = t2;
    }
    
    bfs(1);
   
}

 

 

 

잡담

카테고리가 그래프라는 것을 알았기 때문에 빠르게 접근할 수 있었을 것이다.

카테고리를 모르고 어떤 문제인지 파악하는 훈련도 필요할 것 같다.