(백준/C++) 16928_뱀과 사다리 게임

뱀과 사다리 게임은 1번 칸에서 시작하여 주사위를 굴려 100번 칸까지 이동하는 게임입니다.

그런데 이때, 뱀 칸과 사다리 칸이 존재하고, 뱀 칸에 도착하면 낮은 칸으로 순간이동하고 사다리 칸에 도착하면 높은 칸으로 순간이동 하게 됩니다.

즉, 16928번: 뱀과 사다리 게임 (acmicpc.net) 문제는 100번 칸까지 이동하면서 최대한 사다리 칸을 이용해 최소한의 주사위 굴림으로 100번 칸까지 이동하는 문제입니다.

---

접근법

이 문제는 그래프 탐색 이론의 최단 거리를 탐색하는 문제이므로 너비 우선 탐색(BFS, Breadth-First Search)을 사용합니다.

즉, 주사위를 굴려가며 사다리칸을 이용하는 것과 주사위의 6으로 이동하는 등… 모든 방법에 대해 탐색을 하면서 최단 거리를 구하면 됩니다.

뱀과 사다리 칸

뱀 칸과 사다리 칸을 이용하게 되면 플레이어의 의사와 상관 없이 해당 칸으로 바로 이동됩니다.

즉, 해당 칸으로 이동하면 다음 탐색 노드를 뱀 칸과 사다리 칸에서 주는 값으로 노드를 탐색하면 됩니다.

이때, 뱀 칸의 경우에는 이전 칸으로 이동하기 때문에 어차피 최단 거리가 될 수 없습니다. 따라서 뱀 칸의 경우에는 이동하지 않는다는 선택지를 사용할 수 있습니다.

방문 노드의 처리

뱀 칸을 사용하면 어차피 최단 거리가 되지 않으니 이 부분을 생략할 수 있습니다.

그럼, 주사위를 굴리는 것으로 이미 방문했던 노드를 탐색하는 것은 어떨까요?

이 부분도 이미 최단 거리가 되지 않으므로 생략할 수 있습니다. 즉, 주사위를 두 번 던져 2+3을 하는 것보다 주사위를 한 번 던져 5칸을 가는게 우리의 목적에 더 맞습니다.

즉, 방문 노드를 관리하여 좀 더 빠르고 메모리 공간 효율적으로 최단 거리를 탐색할 수 있습니다.

---

풀이

저는 보드 배열을 사용하여 직접 뱀이나 사다리로 이동할 칸의 정보를 저장했습니다.

또한 Info 구조체를 사용하여 현재 칸과 주사위를 굴린 획수(cnt)를 함께 관리하도록 설계했습니다.

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

struct Info // 현재 위치와 주사위를 굴린 횟수를 저장
{
	int pos;
	int cnt;
};

void makeBoard(vector<int>& board)
{
	// 사다리나 뱀이 있는 칸 설정
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N + M; i++)
	{
		int start, end;
		cin >> start >> end;
		board[start] = end;
	}
}

int search(const vector<int>& board)
{
	queue<Info> q;
	// 방문 여부를 저장한다.
	// 뱀 칸을 이용해 이전 칸으로 이동하면 어차피 최소 횟수가 아니기 때문에 반복 계산할 필요가 없다.
	vector<bool> visited(101, false);

	// 첫 번째 칸에서 시작
	q.push({ 1, 0 });
	visited[1] = true;

	while (!q.empty())
	{
		Info cur = q.front();
		q.pop();

		// 만약 도착했다면 종료
		if(cur.pos == 100)
		{
			return cur.cnt;
		}

		// 모든 주사위의 경우의 수를 탐색
		for(int dice = 1; dice <= 6; dice++)
		{
			int nextPos = cur.pos + dice;

			// 범위를 벗어나거나 방문했다면
			if(nextPos > 100 || visited[nextPos])
				continue;

			// 사다리가 있다면
			if (board[nextPos] != 0)
				nextPos = board[nextPos]; // 사다리를 타고 이동

			visited[nextPos] = true;
			q.push({ nextPos, cur.cnt + 1 });
		}
	}

	return -1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	vector<int> board(101);
	makeBoard(board);

	cout << search(board);
}