[백준 C++] 16928 뱀과 사다리 게임 - 너비 우선 탐색

16928번: 뱀과 사다리 게임

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

int Depth[101];
bool Visited[101];
int Event[101];
queue<int> SearchQueue;

int BFS(int Start, int End)
{
	SearchQueue.emplace(Start);
	Depth[Start] = 0;

	while (!SearchQueue.empty())
	{
		int Current = SearchQueue.front();
		SearchQueue.pop();

		if (Visited[Current])
		{
			continue;
		}

		Visited[Current] = true;

		// Snakes or Ladders
		int Neighbor = Event[Current];
		if (Neighbor != 0)
		{
			if (!Visited[Neighbor])
			{
				Depth[Neighbor] = min(Depth[Neighbor], Depth[Current]);
				SearchQueue.emplace(Neighbor);
			}

			continue;
		}

		// Dice
		for (int i = 1; i <= 6; ++i)
		{
			Neighbor = Current + i;
			if (Neighbor <= 100 && !Visited[Neighbor])
			{
				Depth[Neighbor] = min(Depth[Neighbor], Depth[Current] + 1);
				SearchQueue.emplace(Neighbor);
			}
		}
	}

	return Depth[End];
}

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

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N + M; ++i)
	{
		int Src, Dst;
		cin >> Src >> Dst;
		Event[Src] = Dst;
	}

	for (int i = 1; i <= 100; ++i)
	{
		Depth[i] = 100;
	}

	cout << BFS(1, 100);
}

---

 

너비 우선 탐색을 이용해서 1번 칸 -> 100번 칸 이동 사이의 최소 주사위 횟수를 구하는 문제입니다.

 

문제를 풀 때 주의해야할 점이 두 가지 있습니다.

 

1. 한 노드에서 사다리 또는 뱀이 존재하면, 주사위를 통해 이동하는 인접 노드 탐색은 스킵한다. (무조건 사다리, 뱀을 통해서 이동해야하기 때문)

2. 인접 노드가 전임자로부터 깊이를 물려받을 때, 이미 저장되어 있는 값과 비교해서 min 값을 저장하도록 해야 한다. (이미 저장된 최소값이 다른 칸에서 탐색하다가 더 큰 값으로 덮어씌워질 수 있기 때문)