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

문제

https://www.acmicpc.net/problem/16928

 

 

문제 분석 

1이라는 위치에서 100이라는 위치로 이동하는 문제이다. 

 

다만 주사위로 1~6칸을 갈 수 있으며, 사다리와 뱀이라는 변수가 존재한다. 

 

사다리는 작은 수에서 큰 수로 올라가며, 뱀은 큰 수에서 작은 수로 내려오는 형태이다. 

 

이 문제는 BFS로 풀 수 있다. 

 

 

알고리즘 설계

방문을 확인할 vector 또는 배열, 사다리 및 뱀을 체크할 vector 또는 배열을 만든다. 

 

이후 사다리와 뱀을 입력받아 연결 시켜준다. 

 

1에서 시작하며 추가로 1 ~ 6을 더하여 계속 방문 확인할 배열과 queue에 넣어준다. 

 

주사위 수에 사다리 또는 뱀이 있다면 움직여준다. 

 

100에 도착하면 while에서 벗어나 몇번쨰에 방문하였는지 확인한다. 

 

 

유의점

사다리 또는 뱀이 있다면 도착한 위치에 번호를 queue에 넣어주어야한다. 

 

주사위를 굴릴 때 100이 넘어가면 out of range가 뜨니 이전에 막아주어야 한다. 

 

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<int> visited;

int main()
{
    int n, m, input1, input2;
    queue<int> q;
    cin >> n >> m;

    graph.resize(101);
    visited.resize(101, 0);

    while (n--)
    {
        cin >> input1 >> input2;
        graph[input1].push_back(input2);
    }
    while (m--)
    {
        cin >> input2 >> input1;
        graph[input2].push_back(input1);
    }

    visited[1] = 1;
    q.push(1);

    while (!q.empty())
    {
        int front = q.front();

        if (front == 100)
            break;

        for (int i = front + 1; i <= front + 6; ++i)
        {
            if (i > 100)
                continue;
            if (visited[i] != 0)
                continue;

            for (int j : graph[i])
            {
                if (visited[j] != 0)
                    continue;
                visited[j] = visited[front] + 1;
                q.push(j);
            }

            if (graph[i].size() != 0)
                continue;

            visited[i] = visited[front] + 1;
            q.push(i);
        }

        q.pop();
    }

    cout << visited[100] - 1;
}