[BOJ] 16928번_뱀과 사다리 게임_BFS (C++)

[문제]

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

뱀과 사다리 게임을 진행할 때, 주사위를 조작해 항상 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을지 구하는 문제이다.

뱀과 사다리 게임에 대해 설명하자면, 게임은 정육면체 주사위를 사용하며, 주사위는 각 면에 1부터 6까지의 수가 하나씩 적혀 있는 평범한 주사위이다. 게임을 진행하는 보드판의 크기는 10x10으로 총 100개의 칸으로 나누어져있으며 각 칸에는 1부터 100까지의 수가 하나씩 순서대로 적혀있다.

플레이어는 주사위를 굴려 나온 수만큼 이동한다. 예를 들어 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어가면 이동할 수 없다. 그리고 도착한 칸이 사다리또는 뱀이 있는 칸이면 대상을 따라 이동한다. 예를 들어 i+4번칸에 95번칸이랑 이어진 사다리가 존재하면 i+4번칸으로 이동한 후 바로 95번칸으로 이동한다.

게임의 목표는 1번칸에서 시작해서 100번칸에 도착하는 것이다.

[사용 알고리즘]

BFS(너비 우선 탐색)

[풀이 핵심]

• bfs를 통해 구현이 가능한 문제이다. bfs의 queue에는 현재 좌표와, 현재 카운트 수를 저장해준다.
• bfs를 돌 때마다 1~6(주사위로 나올 수 있는 수)까지 반복해서 다음 좌표값을 구하고 먼저 사다리와 뱀을 통한 이동을 처리해준 후, 사다리와 뱀이 없다면 주사위를 통한 이동을 처리해주며 count(주사위를 굴린 횟수)를 늘려주면된다.
• bool타입 visited[] 배열을 사용해서 꼭 방문처리를 해주자. 이전에 방문한적 있는 좌표를 또 방문하는 것은 무조건 손해(count의 값이 이전에 방문했을 때보다 무조건 높음)이기 때문에 다시 방문할 필요가 없다. <방문처리를 안해주면 메모리초과가 뜬다.>

[코드]

//boj16928번_뱀과 사다리 게임_그래프

#include<iostream>
#include<queue>

using namespace std;

int graph[101];
bool visited[101];

void BFS(int V) {
	queue<pair<int, int>> q;
	q.push({ V,0 });

	while (!q.empty()) {
		int cur_v = q.front().first;
		int count = q.front().second;
		visited[cur_v] = true;

		q.pop();

		for (int i = 1; i <= 6; i++) {
			int next_v = cur_v + i;

			if (next_v == 100) {
				cout << count + 1;
				exit(0);
			}

			if (next_v < 100) {
				if (graph[next_v] != 0) {
					next_v = graph[next_v];
				}

				if (!visited[next_v]) {
					q.push({ next_v,count + 1 });
				}
			}
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int v1, v2;
		cin >> v1 >> v2;

		graph[v1] = v2;
	}

	for (int i = 0; i < M; i++) {
		int v1, v2;
		cin >> v1 >> v2;

		graph[v1] = v2;
	}

	BFS(1);

	return 0;
}