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

www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

---

• 목표지점 100 까지 주사위를 최소로 던져서 가야 한다.
• 주사위의 값을 정할 수 있기 때문에, 주사위를 한번 던질 때 가능한 모든 경우를 하나의 너비로 보고 bfs 를 돌린다.
• 뱀을 타고 내려와서 목적지에 더 가까운 사다리를 탈 수도 있기 때문에, 뱀을 무시하고 사다리만 타는 그리디한 방식으로 접근하면 안된다.

---

#include <iostream>
#include <queue>

using namespace std;

int N, M, temp1, temp2;
pair<int,int> ladders[30];      // 사다리와 뱀 둘 다 포함
bool visited[101];
int answer = 0;

int main(void)
{
    cin >> N >> M;
    for(int i = 0 ; i < N + M ; i++)
    {
        cin >> temp1 >> temp2;
        ladders[i] = {temp1, temp2};
    }

    queue<int> q;
    q.push(1);
    visited[1] = true;          // 1 에서 출발하여 bfs 시작

    while(true)
    {
        int sz = q.size();
        for(int s = 0 ; s < sz ; s++)
        {
            int cur = q.front();
            q.pop();
            
            for(int i = 1 ; i <= 6 ; i++)           // 주사위 1~6 까지 모두 고려
            {
                int next = cur + i;
                if(visited[next]) continue;         // 이전에 방문한 위치면 스킵
                visited[next] = true;
                for(int n = 0 ; n < N + M ; n++)    // 사다리나 뱀에 연결된 위치라면
                {
                    if(next == ladders[n].first)
                    {
                        next = ladders[n].second;   // 타고 올라가거나 내려감
                        break;
                    }
                }
                if(next > 100) continue;

                if(next == 100)                     // 다음 위치가 목적지라면 종료
                {
                    cout << answer+1 << endl;
                    return 0;
                }

                q.push(next);
            }
        }
        answer++;
    }
}