백준 16928번 : 뱀과 사다리 게임

문제링크 : https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 문제설명 

 

1. 주사위를 이용하여 1번 칸에서 100번칸으로  이동하여야한다.

2. 중간에 사다리를 이용하면 더 높은 곳으로 갈 수있고, 뱀을 이용하면 더 낮은 곳으로 움직일 수있다.

3. 주사위,사다리,뱀을 이용하여 100번칸으로 갈 수있는 주사위를 최소 몇번 굴려야 하는지 출력

 

 알고리즘 

 

1. 사다리와 뱀을 구분하지말고 입력 받은뒤 정렬 해준다.

2. bfs 를 이용하여 현재 위치에서 주사위를 굴려 갈 수있는 칸을 모두 구해주고 

3. 100번 칸에 도착했을 떄 BFS의 깊이(DEPTH) 를 출력 하면된다.

 

 코드 

 

#include<iostream>
#include<vector>
#include<queue>
 
 
using namespace std;
typedef pair<int, int>  p;
vector<p> v;
int N, M, visited[101], result = 0;
 
int number(int n) {
 
    //뱀이나 사다리를 만나면 
    for (int i = 0; i < N + M; i++) {
        if (v[i].first == n)return v[i].second;
    }
 
    //안 만나면
    return n;
 
}
 
void bfs() {
    queue<int> q;
    visited[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int Size = q.size();
        
        for (int i = 0; i < Size; i++) {
            int x = q.front();
            q.pop();
 
            //갈수있는 칸 다넣어
            for (int j = 1; j <= 6; j++) {
                if (x + j <= 100 && !visited[x + j]) {
                    int y = number(x + j);
                    q.push(y);
                    visited[y]=1;
                }
            }
 
            if (visited[100])return;
        }
        result++;
    
    }
 
 
}
 
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> N >> M;
 
    for (int i = 0; i < N + M; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back(p(a, b));
    }
    bfs();
    cout << result+1;
 
 
}