BOJ (C/C++) 16928번: 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

---

풀이

모든 위치의 초기값을 자기 자신으로 설정하고, 뱀과 사다리를 이용해 이동해야 할 경우 이동한 위치를 저장했다.BFS를 통해 최단 거리를 탐색할 때에도 이동한 최종 위치를 큐에 삽입하고 계산했다.

---

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int board[101], visited[101];

int BFS(int R) {
	int now, cnt, next;
	queue <pair<int, int>> Q;

	// init
	visited[R] = 1;
	Q.push({ R,1 });

	while (!Q.empty()) {
		now = Q.front().first, cnt = Q.front().second;
		Q.pop();

		for (int i = 6; i >= 1; i--) {
			next = now + i;

			if (next > 100 || visited[next]) continue;
			if (next == 100) return cnt; // 시작이 1이라 cnt+1 X

			// 사다리, 뱀을 이용해 이동한 최종 위치에 cnt 저장 및 큐에 삽입
			visited[board[next]] = cnt + 1;
			Q.push({ board[next],cnt + 1 });
		}
	}
}

int main() {
	int N, M;
	int x, y, u, v;

	// 모든 위치를 자기 자신으로 초기화
	for (int i = 1; i <= 100; i++) board[i] = i;

	scanf("%d %d", &N, &M);

	// 뱀과 사다리로 이동이 있을 때 해당 노드의 위치 변경
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &x, &y);
		board[x] = y;
	}
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &u, &v);
		board[u] = v;
	}

	printf("%d", BFS(1));

	return 0;
}