[알고리즘] 백준 16928번: 뱀과 사다리 게임 (C++), BFS 응용 (1차원)

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

16928번: 뱀과 사다리 게임

저번에는 안 풀리던 문제였는데 오랜만에 시도해보니 풀렸다. 저번 코드는 잘 기억나진 않지만 이번에 한 거보다 더 복잡했던 거 같은데 기억이 안 난다. 여러 가지 경우를 계속 생각했었던 거 같다. 기억나는 건 이런 경우?

하지만, 구현한 코드에서는 상관없다!

주사위를 굴렸을 때 나오는 모든 경우(1 ~ 6)를 다 따지기 때문이다!

 

이번 문제는 '응용력' 체크였던 거 같다. BFS로 이 문제를 풀 수 있는 거 같은데 어떻게 풀어야 할까 고민을 많이 했던 문제다. 아무래도 고민이 많아서 여러 가지 구현해보느라 저번 코드가 길어졌던 거 같다.

 

구현은 다음 순서와 같다.

1. 어떠한 인덱스로 갔을 때, 뱀이나 사다리가 있다면 그 위치의 값을 넣어준다.

2. 나머지 인덱스는 현재 위치를 넣어준다. (이동하지 않음을 나타낸다.)

3. 1부터 BFS를 돌려서 방문을 했다면 (visited가 아닌 cnt 배열 사용) 방문하지 않게끔 한다. (뱀을 밟았을 때 나오는 무한 루프 방지)

4. cnt 배열에는 주사위를 몇 번 돌렸는지 cnt 하는 횟수를 위치당 담는다.

 

처음엔 2차원 배열로 어떻게 풀어야 할지 고민했는데 문제들에서 점점 많은 생각을 요구한다.

포인트는 어떤 위치를 밟았을 때 어디로 가는지 혹은 그 자리에 있는지를 나타낼 수 있는 1차원 배열을 생각할 수 있는 거였던 거 같다.

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

int n, m;
int moves[101] = { 0, };
int cnt[101] = { 0, };

void bfs(int value) {
	queue<int> q;
	q.push(value);
	while (!q.empty()) {
		int idx = q.front();
		q.pop();
		for (int i = 1; i <= 6; i++) {
			int next = idx + i;
			if (next > 100) {
				continue;
			}
			next = moves[next];
			if (cnt[next] == 0) {
				cnt[next] = cnt[idx] + 1;
				q.push(next);
			}
		}
	}
}

int main() {
	cin >> n >> m;

	for (int i = 1; i <= 100; i++) {
		moves[i] = i;
	}
	
	for (int i = 1; i <= n + m; i++) {
		int value, value2;
		cin >> value >> value2;
		moves[value] = value2;
	}

	bfs(1);
	cout << cnt[100];
	return 0;
}