백준 16928 뱀과 사다리 게임 / C++"

문제 : 16928

풀이 point

숨바꼭질과 비슷한 유형이다.
map배열에 뱀을 통해 가는 곳, 사다리를 통해 가는 곳을 저장해둔다.
bfs 순회를 통해 거리를 알아낸다.

풀이 방법

32 62라면 map[32] = 62를 저장해둔다.
주사위는 1 ~ 6이므로 for문을 1에서 6까지 돌리면서 경우의 수를 본다.
만약 주사위를 돌렸을 때 6이 나온다면 map[6]을 본다. map[6]에 뱀이나 사다리가 있으면
그리로 이동한다. 거리를 증가시킨다. 거리 배열을 통해 visit을 대체한다.

코드

//백준 16928, 뱀과 사다리 게임

#include <iostream>
#include <queue>

int dist[101];
int map[101];

void bfs(){
    std::queue<int> q;
    dist[1] = 1;
    q.push(1);
    while(!q.empty()){
        int curr = q.front(); q.pop();
        for(int i{1}; i<=6; ++i){
            int nx = curr + i;
            if(nx > 100) continue;
            if(dist[nx] > 0 || dist[map[nx]] > 0) continue;
            if(map[nx] != 0){
                q.push(map[nx]);
                dist[map[nx]] = dist[curr] + 1;
            }
            else{
                q.push(nx);
                dist[nx] = dist[curr] + 1;
            }
        }
    }
}

int main (){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    
    int N, M;
    std::cin >> N >> M;
    
    int x, y;
    for(int i{0}; i<N; ++i){
        std::cin >> x >> y;
        map[x] = y;
    }
    
    int u, v;
    for(int i{0}; i<M; ++i){
        std::cin >> u >> v;
        map[u] = v;
    }

    bfs();
    std::cout << dist[100]-1;

    return 0;
}