알고리즘

  1. BFS로 가능한 경우를 찾아가면 된다.

  2. 그런데 주의점은, 뱀을 타는게 더 이득일 경우가 있다는 것만 주의하자

    ex)

    2 1
    2 60
    30 99
    65 29

코드

#include <bits/stdc++.h>
 
using namespace std;
 
int N, M, box[110];
list<pair<int,int>> q;
bool visited[110];
 
int BFS();
 
int main() {
	cin >> N >> M;
	int t;
	for (int i = 0; i < N; i++) {
		cin >> t;
		cin >> box[t];
	}
	for (int i = 0; i < M; i++) {
		cin >> t;
		cin >> box[t];
	}
	cout << BFS();
}
 
int BFS() {
	visited[1] = true;
	q.push_back({ 1,0 });
	int result = 2000000000;
	while (!q.empty()) {
		int cur = q.front().first, count = q.front().second;
		q.pop_front();
 
		if (cur == 100) {
			result = min(result, count);
			continue;
		}
		else if (cur > 100)
			continue;
 
		for (int i = 1; i <= 6; i++) {
			int next = cur + i;
			if (!visited[next]) {
				if (box[next] != 0) {
					q.push_back({ box[next], count + 1 });
					visited[box[next]] = true;
				}
				else
					q.push_back({ next, count + 1 });
				visited[next] = true;
			}
		}
	}
	return result;
}