[C++] BaekJoon 16928 뱀과 사다리 게임

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

---

뱀과 사다리 게임을 플레이할 때, 1번 칸에서 100번 칸까지 도착하기 위해 주사위를 최소로 굴린 횟수를 구하는 문제이다.

이때 여기서 주어진 입력은 사다리와 뱀의 정보가 주어진다. 

 

최단 경로를 찾아야 하며, 그러기 위해서는 모든 칸을 탐색해야 하고, 방문한 칸을 체크하여 중복으로 방문하는 것을 막아야하니 BFS로 계산하는게 효율적이겠다고 판단하여 BFS로 구현하였다. 

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <climits> // INT_MAX 사용을 위해 추가

using namespace std;

vector<pair<int, int>> ladder;
vector<pair<int, int>> snake;
vector<int> moves(101, INT_MAX); // 칸 별 이동 횟수를 저장하는 배열
vector<bool> visited(101, false); // 방문 여부를 저장하는 배열

// BFS 알고리즘을 사용하여 최소 이동 횟수를 계산하는 함수
int bfs() 
{
    queue<int> q;
    q.push(1); // 시작 칸은 1번 칸
    visited[1] = true;
    moves[1] = 0; // 시작 칸의 이동 횟수는 0

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

        // 현재 칸에서 주사위를 던진 결과로 이동할 수 있는 칸을 확인
        for (int i = 1; i <= 6; i++) 
        {
            int next = current + i; // 다음 이동할 칸
            if (next > 100) continue; // 100을 초과하는 칸은 무시

            // 사다리를 타거나 뱀을 타는 경우 해당 칸으로 이동
            for (const auto& ladder_pos : ladder) 
            {
                if (ladder_pos.first == next)
                {
                    next = ladder_pos.second;
                }
            }
            for (const auto& snake_pos : snake) 
            {
                if (snake_pos.first == next)
                {
                    next = snake_pos.second;
                }
                
            }

            // 다음 칸을 방문하지 않았다면 이동 횟수를 업데이트하고 큐에 추가
            if (!visited[next]) 
            {
                visited[next] = true;
                moves[next] = moves[current] + 1;
                q.push(next);
            }
        }
    }

    return moves[100]; // 100번 칸의 이동 횟수 반환
}

int main() 
{
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; i++) 
    {
        int x, y;
        cin >> x >> y;
        ladder.push_back(make_pair(x, y));
    }
    for (int i = 0; i < M; i++) 
    {
        int u, v;
        cin >> u >> v;
        snake.push_back(make_pair(u, v));
    }

    int result = bfs(); // 최소 이동 횟수 계산
    cout << result << endl;

    return 0;
}

 

설명

ladder vector와 snake vector는 각각 사다리와 뱀위 정보를 저장한다. 

각 벡터의 요소는 pair로 선언했으며, 첫 번째 요소는 출발지점, 두 번째 요소는 도착 지점을 나타낸다. 

 

bfs() 함수에서 bfs 알고리즘을 실행한다. 

처음부터 출발해야 하므로 1번 칸에서 시작하여 100번 칸 까지 최소 이동 횟수를 계산한다. 

 

이 코드는 다음과 같은 과정을 거쳐 동작한다. 

I. 시작 칸을 큐에 넣고 방문 표시를 한다. (visited[] = true)
II. 큐에서 칸을 하나씩 꺼내어 주사위를 던져 이동 가능한 칸을 찾는다. 
III. 해당 칸에 사다리나 뱀이 있는지 확인하여 도착 칸을 업데이트하고, 방문하지 않은 칸이면, 큐에 넣고
이동 횟수를 업데이트한다. 
IV. 큐가 빌 때 까지 이 과정을 반복하여 결과를 출력