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

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

16928번: 뱀과 사다리 게임

풀이

DP로 풀려했으나 DAG가 아니라서 DP를 적용하기 어렵다는 게시글을 보았다...

최단거리이기 때문에 BFS로 해결하면 된다.

1. 이때, 사다리나 뱀을 만나면 무조건 그 위치로 이동(셋 중 하나만 push 해야 함)하는 것에 주의해야한다.

2. 새로운 도착 방법의 주사위 굴리는 횟수가 기존보다 더 적은지 비교해 참이라면 업데이트 하고 다시 push 한다.

#include <iostream>
#include <unordered_map>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int N, M, a, b; 
/*
사다리만 타면서 도착
*/
int dp[101]; 

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("input.txt", "r", stdin);
    cin >> N >> M;
    
    unordered_map<int, int> ladder;
    unordered_map<int, int> snake;
    vector<int> ch(101, 2147000000);
    for (int i=0; i<N; i++){
        cin >> a >> b;
        ladder[a]=b;
    }

    for (int i=0; i<M; i++){
        cin >> a >> b;
        snake[a]=b;
    }  

    queue<int> q;
    q.push(1);
    ch[1]=0;

    while (!q.empty()){
        int v = q.front();
        q.pop();

        for (int i=1; i<=6; i++){
            int nv = v+i;
            
            if (nv > 100) continue;
            // 만날 수 있는건 셋중 하나임
            if (ladder.find(nv)!=ladder.end()){
                if (ch[ladder[nv]] > ch[v]+1) {
                    ch[ladder[nv]]=ch[v]+1;
                    q.push(ladder[nv]);
                } 
            }
            if (snake.find(nv)!=snake.end()){
                if (ch[snake[nv]]>ch[v]+1) {
                    ch[snake[nv]]=ch[v]+1;
                    q.push(snake[nv]);
                }
            }
            
            if (ladder.find(nv)==ladder.end() && snake.find(nv)==snake.end()){
                if (ch[nv] > ch[v]+1){
                    ch[nv]=ch[v]+1;
                    q.push(nv);
                }
            }
            
        }
    }

    cout << ch[100] << endl;
    return 0;
}