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

 

[적용한 알고리즘]

BFS

 

[아이디어]

숨바꼭질 문제와 동일한데, map에 정보 몇개만 표시해주면 되겠다. 

순간이동? 같은 느낌으로.

 

[생각의 흐름 / 절차] 

BFS 1차원으로 그냥 해결하면 될 것 같다.

 

[교훈]

시간이 없어서 쉬운 문제라도 몇개 풀어놔야 마음이 편안할 것 같아 

일단 해봤다.

 

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

int map[200];
int visited[200];
int n, m;
queue<int> q;
int dist[200];

void bfs(){
    q.push(1);
    visited[1] = true;
    while (!q.empty()){
        int cur = q.front();
        q.pop();

        for (int i = 1; i <= 6; i++){
            int nxt = cur + i;
            if (nxt > 100) continue;
            if (map[nxt] > 0) nxt = map[nxt];
            if (!visited[nxt]){
                visited[nxt] = true;
                q.push(nxt);
                dist[nxt] = dist[cur] + 1;
            }
        }
    }
}
int main(){
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        map[x] = y;
    }
    for (int i = 0; i < m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        map[x] = y;
    }
    bfs();

    printf("%d", dist[100]);
    return 0;
}