뱀과 사다리 게임 (feat. 백준, 16928번)

뱀과 사다리 게임
https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int ans[101];
int N, M;
int check[101];
void bfs(register int p) {
	ans[p] = 1;
	queue<int> q;
	q.push(p);
	while (!q.empty()) {
		auto v = q.front(); q.pop();
		p = v;
		for (register int i = 1, np; i <= 6; ++i) {
			np = p + i;
			if (np <= 100 && ans[np] == 0) {
				ans[np] = ans[p] + 1;
				if (check[np]) {
					if (ans[check[np]] == 0)
						ans[check[np]] = ans[np], q.push(check[np]);
				}
				else
					q.push(np);
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	memset(ans, 0, sizeof(ans[0]) * 101);
	memset(check, 0, sizeof(check[0]) * 101);
	cin >> N >> M;
	for (register int n = 0, x, y; n < N; ++n)
		cin >> x >> y, check[x] = y;
	for (register int m = 0, x, y; m < M; ++m)
		cin >> x >> y, check[x] = y;
	bfs(1);
	cout << ans[100] - 1;
	return 0;
}
// *&)*@*

1. 현재칸에서 1~6칸을 이동할 수 있으므로 현재칸 + 1~6칸은 현재칸까지의 주사위를 굴린 횟수 +1 을 취해줍니다.
2. 사다리의 시작점에 도착한다면 시작점까지의 주사위를 굴린 횟수를 사다리의 도착점에 삽입하고 도착점을 큐에 넣어주게 됩니다.
3. 뱀의 시작점에 도착한다면 시작점까지의 주사위를 굴린 횟수를 뱀의 도착점에 삽입하고 도착점을 큐에 넣어주게 됩니다.
4. 이러한 과정이 100칸까지 갈때까지 반복하고, 100칸이 되면 게임을 종료합니다.
5. 주사위 횟수의 최소값을 구하는 것이므로 BFS로 풀이합니다.