[baekjoon 16928] 뱀과 사다리 게임 (BFS) (C++)

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

16928번: 뱀과 사다리 게임

최소한의 주사위를 굴려서 100까지 가야 하고, 가는 도중에 사다리와 뱀이 있다.

사다리에 해당하면 도착점(100)에 가까워지고, 뱀을 만나면 시작점(1)과 가까워진다.

 

1. 한 칸에 뱀과 사다리가 이중으로 나오는 경우가 없다고 했으니 1차원 배열에 뱀과 사다리를 모두 입력받았고,

2. 주사위를 통해 (1~6)까지의 이동을 할 수 있으므로 BFS를 하며 탐색을 하되,

3. 최소 거리를 구해야 하므로 1차원 거리 저장 배열을 선언해서 만약 현재 위치에서의 주사위 횟수보다 더 적은 횟수로 현재 위치를 올 수 있으면 배열의 값을 갱신해주며 큐에 넣어주었다.

4. 따라서 첫 거리 배열은 모두 무한대 값으로 초기화해주었다. (방문 체크의 역할 + 거리 갱신의 역할을 한다)

 - 처음 무한대 값의 경우 : 방문하지 않은 위치이므로 무조건 큐에 들어가서 다음 bfs가 수행된다.

 - 이미 갱신된 값이 있는 경우 : 그 위치를 방문한 횟수보다 더 적은 횟수로 방문할 수 있는 케이스가 있으면 이 케이스를 이용해서 bfs를 수행.

 

#include <iostream>
#include <queue>

using namespace std;

int N, M, x, y;
int moving[101], record[101];

void BFS(int start) {
	queue < pair<int, int>> q;
	q.push(make_pair(start, 0));
	record[start] = 0;

	while (!q.empty()) {
		int now = q.front().first;
		int count = q.front().second;
		q.pop();

		for (int i = 1; i <= 6; i++) {
			int tempCount = count; // 6번 모두 같은 횟수에서 계산되어야하므로 임시변수 이용
			if (now + i > 100) // 주사위를 던져서 100을 넘어가면 pass
				continue;
			int next = now + i; // 주사위 돌린 이후 값
			tempCount++;
			if (moving[next] != 0) { // 만약 주사위로 이동한 위치에 뱀 또는 사다리가 있다면
				next = moving[next];
			}
			if (record[next] > tempCount) { // 이동 후 기존 주사위 횟수보다 더 적은 횟수로 도착할 수 있다면
				record[next] = tempCount;
				q.push(make_pair(next, tempCount));
			}
		}
	}
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= 100; i++) {
		record[i] = 987654321;
	}
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		moving[x] = y;
	}
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		moving[x] = y;
	}

	BFS(1);

	cout << record[100];
}