백준 16928번 - 뱀과 사다리 게임(C++)

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

16928번: 뱀과 사다리 게임

 

다익스트라, 그래프 등 많은 것을 고민했지만 그냥 bfs 풀이가 가장 쉬운 풀이이다. 

 

#include <iostream>
#include <queue>
#include <map>

using namespace std;

map<int, int> jump;
bool visited[101] = { false, };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= 100; i++) {
		jump.insert({ i, -1 });
	}

	for (int i = 0; i < N + M; i++) {
		int a, b;
		cin >> a >> b;
		jump[a] = b;
	}

	queue<pair<int, int>> q;
	q.push({ 1, 0 });
	int answer = 0;
	while (!q.empty()) {
		int cnt = q.front().second;
		int idx = q.front().first;
		q.pop();
		//cout << idx << endl;
		if (idx == 100) {
			answer = cnt;
			break;
		}

		for (int i = 1; i <= 6; i++) {
			int next = idx + i;
			if (visited[next] == false) {
				if (jump[next] == -1) {
					q.push({ next, cnt + 1 });
					visited[next] = true;
				}
				else {
					q.push({ jump[next], cnt + 1 });
					visited[next] = true;
					visited[jump[next]] = true;
				}
			}
		}
	}

	cout << answer << '\n';
}