백준, BOJ, 16928번, 뱀과 사다리 게임 C++ [CPP] ★★★★★

은근히.. 헷갈렸다.

사실 쉬웠는데.. 헷갈렸다. 짜증난다 ㅠㅠㅠ

BFS문제면서 DP 문제라고 생각하면 되겠다.

 

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

 

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> fromTo;

//보드
int dist[101];

//array[출발]=도착
int arr[101];

int main(){
    int N, M;
    cin >> N >> M;
    for(int i = 0; i<N+M; i++){
        int start, finish;
        cin >> start >> finish;
        arr[start] = finish;
    }

    
    //배열초기화(시작주소, 종료주소(얼만큼 할지), 값)
    fill(dist, dist+101, -1);
    
    //1부터 BFS로 시작
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        //주사위 굴리기
        for(int i = 1; i<=6; i++){
            int nextPos = cur + i;
            //100 넘어서 가지 못함
            if(nextPos > 100)continue;
            
            
            //주사위를 던져 도착한 위치가 뱀이나 사다리가 있는지 체크 => 있으면 바로 그 위치로감
            //있으면 (연속으로 타는 경우는 존재하지 않음)
            //더 긴 경로는 조사하지 않음
            if(arr[nextPos] != 0){
                if(dist[arr[nextPos]] > dist[cur] + 1 || dist[arr[nextPos]] == -1){
                    q.push(arr[nextPos]);
                    dist[arr[nextPos]] = dist[cur] + 1; 
                }
            }else{
                if(dist[nextPos] == -1 || dist[nextPos] > dist[cur] + 1){
                    dist[nextPos] = dist[cur] + 1;
                    q.push(nextPos);
                }
            }
        }
    }
    
    cout << dist[100];
    
    return 0;
}