뱀과 사다리 게임 최소 주사위 횟수 구하기 – BFS 알고리즘 완벽 가이드

뱀과 사다리 게임이란?

뱀과 사다리(Snake and Ladder)는 누구나 한 번쯤 즐겨본 고전 보드게임입니다. 게임판에는 번호가 매겨진 여러 칸이 있으며, 일부 칸은 사다리 또는 뱀으로 연결되어 있습니다.

• 사다리를 만나면 순서대로 이동하지 않고도 한 번에 더 높은 칸으로 올라가 목적지에 가까워질 수 있습니다.
• 뱀을 만나면 반대로 더 낮은 칸으로 내려가 그 지점부터 다시 여정을 시작해야 합니다.

이 문제에서 우리가 구해야 할 것은 시작 칸에서 도착 칸까지 도달하는 데 필요한 최소 주사위 던지기 횟수입니다.

문제 접근 방식: BFS(너비 우선 탐색)

주사위를 한 번 던질 때마다 1칸에서 6칸까지 이동할 수 있으므로, 이 문제는 각 칸을 정점(vertex)으로, 주사위 한 번의 이동을 간선(edge)으로 보는 가중치 없는 그래프의 최단 경로 문제로 해석할 수 있습니다. 따라서 너비 우선 탐색(BFS)을 활용하면 최소 이동 횟수를 효율적으로 구할 수 있습니다.

입력 및 출력 예시

입력:
뱀과 사다리의 시작 위치와 끝 위치

뱀: 26 → 0, 20 → 8, 16 → 3, 18 → 6
사다리: 2 → 21, 4 → 7, 10 → 25, 19 → 28

출력:
필요한 최소 주사위 던지기 횟수는 3

알고리즘 설계

minDiceThrow(move, cell)

입력: 뱀이나 사다리의 도약 위치 정보 배열(move), 전체 칸의 개수(cell)
출력: 마지막 칸에 도달하기 위해 필요한 최소 주사위 던지기 횟수

Begin
   모든 칸을 방문하지 않음(unvisited)으로 초기화한다.
   큐(queue) q를 선언한다.
   시작 정점을 방문 처리한다.

   시작 정점의 번호 := 0, 거리(dist) := 0으로 설정하고
   시작 정점 s를 큐 q에 삽입한다.
   큐가 비어있지 않은 동안 반복한다:
      qVert := 큐의 맨 앞 요소
      v := qVert의 정점 번호
      if v = cell - 1이면  // 마지막 정점에 도달한 경우
         반복문을 종료한다.
      큐에서 하나의 항목을 삭제한다.
      for j := v + 1 부터 v + 6까지, 단 j < cell인 동안 j를 1씩 증가시키며:
         if j를 방문하지 않았다면:
            newVert.dist := (qVert.dist + 1)
            j를 방문 처리한다.
         if 해당 위치에 뱀이나 사다리가 있다면:
            newVert.vert := move[j]  // 해당 위치로 점프
         else:
            newVert.vert := j
         newVert를 큐에 삽입한다.
   반복 종료
   return qVert.dist
End

C++ 구현 예제

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

struct vertex {
   int vert;
   int dist;     // 시작점으로부터 이 정점까지의 거리
};

int minDiceThrow(int move[], int cell) {
   bool visited[cell];
   for (int i = 0; i < cell; i++)
      visited[i] = false;     // 처음에는 모든 칸을 방문하지 않음으로 설정

   queue<vertex> q;

   visited[0] = true;     // 0번 칸에서 시작
   vertex s = {0, 0};
   q.push(s);           // 0번 정점을 큐에 삽입

   vertex qVert;
   while (!q.empty()) {
      qVert = q.front();
      int v = qVert.vert;

      if (v == cell-1)    // v가 목적지 정점인 경우
         break;

      q.pop();
      for (int j=v+1; j<=(v+6) && j<cell; ++j) {    // 다음 1~6칸 확인
         if (!visited[j]) {
            vertex newVert;
            newVert.dist = (qVert.dist + 1);     // 거리 1 증가
            visited[j] = true;

            if (move[j] != -1)
               newVert.vert = move[j];     // j번째 칸에 뱀이나 사다리가 있는 경우
            else
               newVert.vert = j;
            q.push(newVert);
         }
      }
   }
   return qVert.dist;     // 최소 주사위 던지기 횟수 반환
}

int main() {
   int cell = 30;      // 총 30개의 칸으로 가정
   int moves[cell];

   for (int i = 0; i<cell; i++)
      moves[i] = -1;        // 처음에는 뱀이나 사다리 없음으로 초기화

   // i번째 칸의 사다리는 move[i] 위치로 점프
   moves[2] = 21;
   moves[4] = 7;
   moves[10] = 25;
   moves[19] = 28;

   // i번째 칸의 뱀은 move[i] 위치로 이동
   moves[26] = 0;
   moves[20] = 8;
   moves[16] = 3;
   moves[18] = 6;

   cout << "필요한 최소 주사위 던지기 횟수는 " << minDiceThrow(moves, cell);
}

실행 결과

필요한 최소 주사위 던지기 횟수는 3

복잡도 분석

시간 복잡도: O(N) — 각 칸을 최대 한 번씩만 방문하며, 방문 시 최대 6개의 인접 칸을 확인합니다. N은 전체 칸의 개수입니다.

공간 복잡도: O(N) — 방문 여부 배열과 큐에 저장되는 정점 정보를 위해 칸 수에 비례하는 메모리가 필요합니다.

마무리

뱀과 사다리 문제는 언뜻 복잡한 시뮬레이션처럼 보이지만, 그래프 이론의 관점에서 바라보면 BFS로 간단히 해결할 수 있는 대표적인 최단 경로 문제입니다. 사다리와 뱀에 의한 점프를 간선으로 모델링하는 것이 핵심 아이디어이며, 이러한 사고방식은 미로 찾기, 최소 이동 횟수 계산 등 다양한 알고리즘 문제에도 응용될 수 있습니다.