[BOJ]16928-뱀과 사다리 게임

16928

#include <iostream>
#include <queue>

using namespace std;

int dist[101];
int loc[101];
int N;

void bfs(int num)
{
    queue<int> q;
    q.push(num);
    while (!q.empty())
    {
        int tmp = q.front();
        q.pop();
        for (int i = 1; i <= 6; i++)
        {
            int next_loc = tmp + i;

            if (next_loc > 100) continue;
            next_loc = loc[next_loc];
            if (dist[next_loc] == -1)
            {
                dist[next_loc] = dist[tmp] + 1;
                q.push(next_loc);
            }
        }
    }

}

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int  M;

    cin >> N >> M;

    for (int i = 1; i <= 100; i++)
    {
        loc[i] = i;
        dist[i] = -1;
    }

    for (int i = 0; i < N + M; i++)
    {
        int tmp1, tmp2;

        cin >> tmp1 >> tmp2;

        loc[tmp1] = tmp2;
    }

    dist[1] = 0;
    bfs(1);

    cout << dist[100];

}

그래프만 생각하다보니 주사위 던지는 부분을 생각하기 어려워 풀이를 보았다.

생각보다 단순하게 풀이가 가능하다.

세상에는 똑똑한 사람이 많아..

참고자료

16928 풀이