뱀과 사다리 게임

문제

언어

  • JavaScript

순서도

  1. BFS 탐색

문제 풀이 step 1

  • 뱀과 사다리 게임을 할 때, 주사위를 조작해 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까요??
  • 게임은 정육면체 주사위를 사용합니다. 주사위의 각 면에는 1 부터 6 까지 숫자가 하나씩 적혀있습니다.
  • 게임은 크기가 10 x 10 이고, 총 100 개의 칸으로 나누어져 있는 보드판에서 진행됩니다.
  • 보드판에는 1 부터 100 까지 수가 하나씩 순서대로 적혀져 있습니다.
  • 플레이어는 주사위를 굴려 나온 수만큼 이동해야 합니다.
    • 예를 들어, 플레이어가 i 번 칸에 있고, 주사위를 굴려 나온 수가 4 라면, i + 4 번 칸으로 이동해야 합니다.
  • 만약 주사위를 굴린 결과가 100 번 칸을 넘어간다면 이동할 수 없습니다.
  • 도착한 칸이 사다리면, 사다리를 타고 위로 올라갑니다.
  • 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 됩니다.
  • 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아집니다.
  • 게임의 목표는 1 번 칸에서 시작해서 100 번 칸에 도착하는 것입니다.
  • 게임판의 상태가 주어졌을 때, 100 번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구하는 문제입니다.

문제 풀이 step 2

  • 우선, 100 크기의 그래프를 생성합니다. 이는 1 차원 배열로 간단히 구현할 수 있습니다.
  • 그리고 주어지는 뱀과 사다리의 정보를 그래프에 입력합니다.
  • 1 번 칸에서 BFS 탐색을 시작합니다.
    • 다음 칸은 주사위를 굴려서 나오는 숫자인 1 ~ 6 까지의 수를 현재 칸에 더한 수입니다.
    • 만약 다음 칸이 이미 방문한 칸이거나 100 을 넘어간다면, 그 경로는 제외시킵니다.
    • 만약 다음 칸에 뱀이 있다면, 뱀을 따라서 내려간 칸을 탐색하고, 반대로 사다리가 있다면, 사다리를 타고 올라간 칸을 탐색하면 됩니다.
    • 매 탐색마다 주사위를 굴린 횟수를 갱신합니다.
  • BFS 탐색 도중 100 번 칸에 도달하면, 100 칸까지 가는데 주사위를 굴린 횟수를 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// Queue 구현
class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(item) {
		this.bucket[++this.rear] = item;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

// 100 번 칸을 넘어가는지 검사
const isPossibleRoute = (pos) => pos <= 100;

// BFS 탐색 함수
const bfs = (graph, distance) => {
	const queue = new Queue();

	// 1 번 칸에서 시작
	distance[1] = 0;
	queue.enqueue(1);

	while (!queue.isEmpty()) {
		const from = queue.dequeue();

		// 주사위를 굴린 후 6 개의 칸으로 이동
		for (let i = 1; i < 7; i++) {
			let to = from + i;

			if (!isPossibleRoute(to)) continue;

			// 뱀이나 사다리가 있는 칸이면, 그에 맞게 칸 이동
			if (graph[to] !== 0) to = graph[to];
			if (distance[to] !== -1) continue;

			// 주사위 굴린 횟수 갱신
			distance[to] = distance[from] + 1;
			queue.enqueue(to);
		}

		// 100 번 칸에 도달했으면, 탐색 종료
		if (distance[100] !== -1) break;
	}

	// 100 번 칸에 도달하기 위해 주사위를 굴린 횟수 반환
	return distance[100];
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);

	// graph 생성 후, 뱀과 사다리 정보 입력
	const graph = Array(101).fill(0);
	for (let i = 1; i < 1 + n; i++) {
		const [x, y] = input[i].split(" ").map(Number);
		graph[x] = y;
	}
	for (let i = 1 + n; i < 1 + n + m; i++) {
		const [u, v] = input[i].split(" ").map(Number);
		graph[u] = v;
	}

	// BFS 탐색 진행
	const distance = Array(101).fill(-1);
	const ans = bfs(graph, distance);

	return ans;
};

console.log(solution(input));