[C++] 16928번: 뱀과 사다리 게임 (BFS)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

1번부터 100까지 있는 게임판에서, 다른 칸으로 이동하는 뱀과 사다리가 주어질 때, 100번칸에 도달하기 위해 굴려야하는 주사위 횟수의 최솟값을 구하여라.

---

시간복잡도 어림하기

BFS 알고리즘

 가중치가 같은(이동할 때는 모두 주사위 한 번) 최단거리를 묻는 문제이므로 BFS를 사용할 수 있습니다. BFS를 사용했을 때, 게임판을 탐색하는 횟수는 최대 100번이지만, 게임판에 있는 뱀과 사다리에 따라 100번보다 더 많이 탐색할 가능성도 있습니다. 

 하지만, 게임판의 크기가 100으로 아주 작고, 다시 되돌아간 경우에도 반드시 재탐색을 하는 것이 아니므로 제한 시간내에 문제를 해결할 수 있을 것입니다. 

---

알고리즘 설계하기

 이 문제는 일반적은 BFS알고리즘에 뱀과 사다리라는 변수가 있는 형태입니다. 따라서 기본 구조는 일반적인 BFS알고리즘을 따릅니다.

 

 하지만, 뱀과 사다리를 통해 한 번에 1부터 6칸이 아닌 더 많은 칸을 이동하거나 다시 뒤로 돌아갈 수도 있습니다. 이전 칸으로 다시 돌아간 경우에는 이미 방문한 칸을 다시 방문할 가능성이 있는데, 이미 방문한 칸이라도 더 적은 횟수로 방문할 가능성이 있으므로 이 경우를 확인해야합니다.

 

 다시 정리해보면,

다음 칸이 뱀 또는 사다리 칸인 경우
 1. 뱀 또는 사다리로 이동한 위치를 방문하지 않은 경우 -> 탐색
 2. 뱀 또는 사다리로 이동한 위치를 이미 방문한 경우
   2-1. 현재 칸과 뱀 또는 사다리를 통해 도달한 횟수가 이미 저장된 최단 횟수보다 작은 경우 -> 탐색

다음 칸이 일반 칸인 경우
 1. 아직 방문하지 않은 경우 -> 탐색
 2. 이미 방문한 경우
  2-1. 현재 칸으로부터 도달하는 횟수가 이미 저장된 최단 횟수보다 작은 경우 -> 탐색

 으로 나눌 수 있습니다.

 

 이와 같은 코드를 구현하기 위해서는 어떤 칸이 일반 칸인지, 뱀 또는 사다리 칸인지 알아야 합니다. 따라서 일반 칸은 0의 값을 가지고, 뱀 또는 사다리 칸에는 연결된 위치의 칸의 번호를 가지는 배열을 사용합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<queue>
using namespace std;

int n, m, a[104], visited[104];
queue<int> q;
int main() {
    cin >> n >> m;
    int from, to;
    for(int i = 0; i < n + m; i++){
        cin >> from >> to;
        a[from] = to;
    }
    
    q.push(1); visited[1] = 1;
    int pos;
    while(!q.empty()){
        pos = q.front(); q.pop();
        for(int i = 1; i <= 6; i++){
            if(pos + i > 100) continue;
            /*다음위치가 뱀 또는 사다리인 경우*/
            if(a[pos + i] > 0 && (visited[a[pos + i]] > visited[pos] + 1 || visited[a[pos + i]] == 0)){
                visited[a[pos + i]] = visited[pos] + 1;
                q.push(a[pos + i]);
            } /*다음위치가 일반 칸인 경우*/
            else if(a[pos + i] == 0 && (visited[pos + i] > visited[pos] + 1 || visited[pos + i] == 0)){
                visited[pos + i] = visited[pos] + 1;
                q.push(pos + i);
            }
        }
    }
    cout << visited[100] - 1;
    return 0;
}

 먼저 시작위치 1을 queue에 넣고 최단 횟수를 1로 초기화 합니다. 이후 queue가 빌 때까지 탐색을 진행합니다.

 

 현재 위치에 대해 1부터 6까지 이동하며 탐색하는 데, 다음 위치가 뱀 또는 사다리인 경우에는 현재 위치에서 해당 위치로 도달하는 방법이 최단 횟수를 가지는지 확인하고 탐색 여부를 결정합니다.

 다음 위치가 일반 칸일 때에도 역시 현재 위치에서 해당 위치로 도달하는 방법이 최단 회수를 가지는지 확인하고 탐색 여부를 결정합니다.

---