백준 [16928] 뱀과 사다리 게임

출처 : https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

	#include<iostream>
	#include<queue>
	using namespace std;
	int map[101];
	bool visited[101];
	void bfs() {
	queue<pair<int, int>> q;
	visited[1] = true;
	q.push({ 1, 0 });
	while (!q.empty()) {
	int cur = q.front().first;
	int cnt = q.front().second;//주사위 굴린 횟수
	q.pop();
	for (int i = 1; i <= 6; i++) {
	int nx = cur + i;
	if (nx == 100) {
	cout << cnt + 1 << '\n';
	return;
	}
	while (map[nx]) {
	nx = map[nx];
	}
	if (!visited[nx]) {
	visited[nx] = true;
	q.push({ nx, cnt + 1 });
	}
	}
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, M, x, y, u, v;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
	cin >> x >> y;
	map[x] = y;
	}
	for (int i = 0; i < M; i++) {
	cin >> u >> v;
	map[u] = v;
	}
	bfs();
	return 0;
	}

view raw 16928.cpp hosted with ❤ by GitHub

bfs

각 칸에 사다리 혹은 뱀이 있을 경우 도착 좌표를 적고, 나머지는 0으로 하여 구별한다.

주사위가 1일때 부터 6일때까지 반복해주고 현재 좌표에 더해서 다음 좌표를 만든다.

다음 좌표가 100일 경우 카운트에 +1해서 출력해준다.

만약 100보다 작을 경우 먼저 다음 좌표에 사다리 혹은 뱀인지 확인해서 0이 아닌 경우 적혀있는 값으로 좌표를 이동해준다. (좌표가 0이 아닐 때까지 반복)

방문을 체크해야하는 이유

-> 주사위를 굴리는 최소 횟수를 찾아야 하는데 처음 방문한 이후에 온 좌표는 무조건 그 앞 좌표보다 느리고 중복이기 때문에 다시 방문할 필요가 없기 때문.