백준 16928번 :뱀과 사다리 게임 (그래프 순회 및 탐색)

문제

뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.

주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?

게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.

플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자.

사다리를 만나서 올라가고 뱀을 만나서 내려오는 게임.

입력

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.

다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.

1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

출력

100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

 

 

----------------------------------------------------------------------------------------------------------------------

1. 문제 해석

100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구하는 것이므로, 주사위의 값이 정해진 것이 아니라 임의로 가장 최적의 조건이 되는 경우에 대해 최소 횟수를 추론하는 문제이다.

각 주사위의 수에 대해 플레이어의 위치가 증가하는데, 위치에  따라 사다리를 만나거나 뱀을 만나면 그 위치가 변경된다. 

기본적으로 각 주사위의 수에 대해 브루트포스법으로 접근하면 값을 구할 수 있을 것이다.

 

<브루트포스>

while(TRUE)문 안에서 주사위의 값을 랜덤으로  (1,1,1,1,1.. ), (1,1,1,1... 2) 로 변경해가면서 플레이어의 위치를 조정하다가 100번째 위치가 되었을 때 최솟값인지 여부에 따라 최소횟수를 조정하면 구할 수 있을 것이라고 판단.

 

그러나 이 방식은 너무 오래 걸린다는 단점이 있다. 

다른 방법에는 어떤 방식이 있을까?

 

 

 

잘 모르겠어서 다른 블로그를 학습하고 돌아왔다. 

다른 사람들이 푼 방식은 다음과 같다. 

1. 평소대로 기본적인 BFS를 수행하되 처음에는 1을 큐에 넣고 수행을 시작한다. 

    기본적인 BFS라 함은, 한 노드를 큐에 넣고 인접노드들을 다시 모두 큐에 넣어서 갈 후보들을 넣고, 또 하나씩 꺼내서 후보를 꺼내서 또 갈 수 있는 후보들을 넣는, 그런데 그 순서가 FIFO 구조이기 때문에 결국 같은 거리에 있는 노드들을 순차대로 방문하게 되는 그것이다. 

2. 인접한 노드에 접근 하는 것을 1~6을 더한 인덱스에 접근하는 것으로 변경한다.

  즉 노드끼리 연결된 것이 배열에서 상하좌우로 이동할 수 있었던 기본문제와 달리, +1, +2, ... +6 노드까지 이동할 수 있는 간선으로 변경된 것이다..! (뱀, 사다리의 경우 추가적인 강제적인 간선)

3. 뱀이나 사다리에 해당하는 인덱스를 접근했을 경우 그 인덱스를 저장한다. 

4. 2,3 번을 반복할 때는 큐에 넣는데 수행횟수를 1 증가 시켜서 넣는다. 

5. 100번 인덱스를 방문하게 되었을 때는 큐에 들어있던 수행횟수를 추출해서 그 값을 저장하고, 출력한다. 

 

 

2. 구현

2.1. BFS

여기서 다시 한번 짚게 되는 BFS의 특징은 다음과 같다 : 

한 노드에 대해서 방문할 수 있는 모든 노드를 큐에 넣는 것은 곧 같은 거리에 있는 모든 노드들을 탐색하게 되는 결과를 낳는다. 이는 곧 최단경로와 이어지게 된다: 원하는 노드에 처음으로 방문하게 되면, 그때까지 이동한 경로 혹은 시간은 최소임을 보장하게 된다.

 

 

이전 까지의 문제들은 모두 거리들을 map에 저장한다음 해당  노드 위치의 배열 값을 불러와서 출력하는 방식을 사용했었는데, 이번 문제를 통해서 거리를 모두 저장할 필요없이 원하는 노드에 도달했다면 그것이 BFS에 의하면 최소 거리,  최소 시간의 비용으로 도착한 것일 것이므로, 그 값을 사용하도록 하는 법을 배웠다.

 

2.2. 구현

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define TRUE 1
#define FALSE 0

int N,M;
using namespace  std;
int visited[130] = {0,};
queue <pair<int, int> > Q;

vector <int> moves[120];

int find()
{
    int answer;
    Q.push(make_pair(1, 0));
    while (!Q.empty())
    {
        int next = Q.front().first;
        int time = Q.front().second;
        Q.pop();
//        printf("next : %d - dis %d\n", next, time);
        if(visited[next] == TRUE)
            continue;
        visited[next] = TRUE;
        if(next >= 100)//종료 조건: 100 인덱스에 접근
        {
            answer = time;
            break;
        }
        for(int i=1;i<=6;i++)
        {
            int next_mv = next + i;
            if (moves[next_mv].size())//다음 인덱스 위치 변경: 뱀이나 사다리인 경우
                next_mv = moves[next_mv].front();
            if (next_mv <= 100)
                Q.push(make_pair(next_mv, time + 1));
            else if(next_mv == 100)
            {
                answer=  time +1;
                break;
            }
//            printf("next move: %d, dis %d\n", next_mv, time+1);
        }
    }
    return answer;
}

int main()
{
    int v,w,ret;
    scanf("%d %d", &N, &M);//사다리, 뱀 수 입력
    for(int i=0;i<N;i++) { //사다리 정보 입력
        scanf("%d %d", &v, &w);
        moves[v].push_back(w);
    }
    for(int i=0;i<M;i++) {//뱀 정보 입력
        scanf("%d %d", &v, &w);
        moves[v].push_back(w);
    }
    ret = find();//1부터 100까지 탐색 시작.
    printf("%d", ret);



}

 

 3. 주의점

평소에 최단경로를 풀 때, 거리 갱신을 위해서 모든 거리를 노드들에 대해 배열에 저장하고, 더 최소일 때만 갱신하면서 저장하는 방식을 사용했었다.  

그러나 이번 방식에서는 원하는 노드에 도달할 때까지 걸리는 거리를 큐 자체에 넣으면서 push를 하고, pop했을 때 원하는 노드에 도달했거나 push하기 직전 노드가 원하는 노드라면 그때의 거리가 곧 최소 거리임을 보장한다는 것을 자꾸만 헷갈려하고 있었다. 

그 이유를 생각해보면, 전자의 경우에는 시작점이 여러군데라서 잘못 갱신된다면 최소 경로를 잃게 되는 데에 반해, 후자의 경우는 시작점이 하나이므로 도달할 수 있는 모든 경로를 하나씩 거리별로 조사하기 때문에, 그때의 거리가 곧 최소 경로임이 확실하게 보장된다는 것을 이해했다. 

 

 

 

 

 

 

--------------------------------------------------------------------------------------------------------------------------------------------------------

 

4. 예시

 

아래 그림을 통해 최소 경로를 이해하는데 도움이 된다면 좋겠다. 

(단, 첫번째 시작점의 시도횟수를 1로 설정했기 때문에 실제 정답보다 1큰 값이 저장되어있다. )

3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17

정답 : 3