BOJ 16928번: 뱀과 사다리 게임

문제

문제 바로가기> BOJ 16928번: 뱀과 사다리 게임

16928번: 뱀과 사다리 게임

 

풀이

사다리와 뱀 정보를 path 배열에 저장해주고, BFS를 통해 문제를 해결할 수 있다.

BFS를 진행하는 이유는 "100번 칸에 도착하기 위해 주사위를 굴려야하는 횟수의 최솟값"을 구해야하기 때문이다.

#include<iostream>
#include<queue>
#define MAX 101
using namespace std;

int N, M;
int path[MAX];
bool visited[MAX];

void input(){
    cin >> N >> M;

    int x, y;
    while (N--){
        cin >> x >> y;
        path[x] = y;
    }
    while(M--){
        cin >> x >> y;
        path[x] = y;
    }
}

int solution(){
    queue<pair<int, int>> q;
    q.push({1, 0});

    while (!q.empty()){
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if (num == 100) return cnt;
        for (int i = 1; i<=6; i++){
            if(visited[num+i]) continue;
            visited[num+i] = true;
            if(path[num+i]!=0) q.push({path[num+i], cnt+1});
            else q.push({num+i, cnt+1});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    cout << solution();
}