취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16928번 문제인 뱀과 사다리 게임이다.
문제는 아래 링크를 확인하자.

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

뱀과 사다리 게임판을 하나의 그래프로 생각해보자.

게임판의 각 칸을 하나의 노드로 생각하고, 각 칸 A에서 주사위를 던져서 (사다리와 뱀 등을 거친 후) 이동하게 되는 칸 B로 이동하는 것을 하나의 에지로 생각할 수 있다.

이 때, 이 문제를 푸는 것은 에지를 최소 몇개를 거쳐서 1에서 100까지 이동할 수 있는가가 된다. 이는 BFS를 이용하여 간단히 해결할 수 있다.

99번 칸에서 6의 주사위눈이 나온다던가 하는 100번칸을 넘어가는 이동이 없다는 점에 신경을 써서 구현하자.

아래는 제출한 소스코드이다.

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

int board[106];
int dist[106];

queue<int> que;
bool visited[106];

void bfs() {
	while (!que.empty()) {
		int current = que.front(); que.pop();
		for (int i = 1; i <= 6; i++) {
			int next = board[current + i];
			if (visited[next]) continue;
			visited[next] = 1;
			dist[next] = dist[current] + 1;
			que.push(next);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 1; i <= 100; i++) board[i] = i;

	int N, M; cin >> N >> M;
	N += M;

	while (N--) {
		int x, y; cin >> x >> y;
		board[x] = y;
	}

	visited[1] = 1;
	que.push(1);
	bfs();

	cout << dist[100];
}