[Gold 5] 16928번 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

 

이 문제는 BFS를 통해 해결할 수 있다.

100칸의 배열을 생성하고 뱀과 사다리와 무관하게 index, value를 통해 배열에 요소를 집어 넣는다.

queue의 값이 100이 되면 반복을 멈추고 이동 횟수를 저장한다.

주사위는 1~6까지 있고, 최대 값은 100까지이므로 조건문으로 제어한다.

뱀과 사다리가 있다면 뱀과 사다리 값을 queue에 삽입하고, 이외에는 주사위 값을 queue에 삽입한다.

 

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

int result;
int graph[101] = { 0, };
int visited[101] = { 0, };
queue<pair<int, int>> q;

void bfs() {
	q.push(make_pair(1, 0));
	visited[1] = 1;
	while (!q.empty()) {
		int v = q.front().first;
		int c = q.front().second;
		q.pop();

		if (v == 100) {
			result = c;
			break;
		}
		c++;
		for (int i = 0; i < 6; i++) {
			int pos = v + (i + 1);
			if (pos > 100) continue;

			if (!visited[pos]) {
				if (graph[pos]) {
					q.push(make_pair(graph[pos], c));
					visited[graph[pos]] = 1;
				}
				else {
					q.push(make_pair(pos, c));
					visited[pos] = 1;
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N + M; i++) {
		int index, value;
		cin >> index >> value;
		graph[index] = value;
	}
	bfs();
	cout << result << '\n';
}