[C++/백준] 16928번: 뱀과 사다리 게임

문제 링크

16928번: 뱀과 사다리 게임

 

풀이

BFS 문제

1. 뱀과 사다리 입력을 받으며 인접리스트 adj를 초기화해준다.
2. BFS를 시작한다.
   1. 주사위 횟수가 담기는 dist 배열을 INF로 초기화해준다. 이 때 INF는 주사위를 1로 돌려 100칸까지 가는 경우가 최대이기 때문에 101로 정의했다.
   2. 첫번째 칸부터 시작해서 queue가 빌 때까지 반복한다.
   3. adj[cur].size()가 0보다 큰 경우는 뱀이나 사다리를 타야하고, 아닌 경우는 주사위를 돌려야하기 때문에 경우를 나누어준다.
   4. 뱀이나 사다리가 있다면 인접 리스트를 확인해 다음 칸의 dist가 현재 칸의 dist보다 클 경우, 다음 칸을 작은 값으로 갱신해준 뒤 q에 넣어준다.
   5. 주사위를 돌릴 경우 1~6까지 주사위를 돌릴 수 있으므로 dist[next] > dist[cur]+1일 경우 갱신해주고 q에 넣어준다. 이 때 100칸을 넘으면 안되므로 continue해준다.
3. dist[100]을 출력하면 끝

 

코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 101
using namespace std;

void BFS(vector<vector<int>> &adj)
{
    vector<int> dist(101, INF);
    queue<int> q;
    dist[1] = 0;
    q.push(1);

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        if (adj[cur].size() > 0) // 뱀이나 사다리가 있으면
        {
            for (int i = 0; i < adj[cur].size(); i++) // 뱀이나 사다리 탈 때
            {
                int next = adj[cur][i];
                if (dist[next] > dist[cur])
                {
                    dist[next] = dist[cur];
                    q.push(next);
                }
            }
        }
        else
        {
            for (int i = 1; i <= 6; i++) // 주사위를 돌릴 때
            {
                int next = cur + i;
                if (next > 100) continue;
                if (dist[next] > dist[cur] + 1) // 주사위 횟수가 갱신될 때
                {
                    dist[next] = dist[cur] + 1;
                    q.push(next);
                }
            }
        }
    }

    cout << dist[100];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(101);
    for (int i = 0; i < n+m; i++)
    {
        int stt, end;
        cin >> stt >> end;
        adj[stt].push_back(end);
    }

    BFS(adj);

    return 0;
}