<Baekjoon> #16928 BFS_뱀과 사다리 게임 c++

#16928 뱀과 사다리 게임

100번칸에 도착하기 위해 최소 굴려야 하는 주사위 횟수를 구하는 문제다. 여기서 '최단 거리'를 구하면 되므로 BFS로 풀어야 한다.

뱀과 사다리를 따로 구분해서 배열을 만들 필요가 없으니 그냥 같이 int ladderOrSnake[MAX] 로 선언해서 뱀과 사다리를 함께 저장해준다.

ladderOrSnake의 모든 곳에 데이터가 채워지는 것이 아니라서 처음에는 hash map을 이용하여 저장하려고 했었다.

unordered_map<int, int> map;
for (int i = 0; i < n + m; i++) {
	cin >> a >> b;
	map[a] = b;
}

그런데 하다보니 map에서 데이터를 꺼내서 저장하는 부분이 해결이 안 돼서 그냥 배열을 만들어서 했다. 어차피 MAX=201이기 때문에 큰 메모리 낭비는 없을 것 같다. (만약에 MAX가 크게 주어졌을 때는 어떻게 해결해야 할 지 모르겠다.)

그 후에는 최단 경로를 계산하는 BFS의 방법으로 푼다.
한 가지 주의할 점은 다음위치=현재의 위치+주사위를 던져서 나온 숫자에서 다음 위치에 해당하는 점이 뱀 또는 사다리 이면 그 위치로 이동을 하고 queue에 추가해준다.

전체코드

#include<iostream>
#include <queue>

using namespace std;
const int MAX = 101;
int ladderOrSnake[MAX];
int dp[MAX];

void bfs() {
	queue <int>q;
	q.push(1);
	dp[1] = 0;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int dice = 1; dice <= 6; dice++) {
			int next = cur + dice;
			if (next > 100) continue;
			if (ladderOrSnake[next]!=0) next = ladderOrSnake[next];
			if (dp[next] != -1) continue;
			dp[next] = dp[cur] + 1;
			q.push(next);
		}
	}
}
int main() {
	memset(dp, -1, sizeof(dp));
	memset(ladderOrSnake, 0, sizeof(ladderOrSnake));
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n + m; i++) {
		int x, y;
		cin >> x >> y;
		ladderOrSnake[x] = y;
	}
	bfs();
	cout << dp[100] << endl;
	return 0;
}