[백준#C++] 뱀과 사다리 게임

문제

https://www.acmicpc.net/submit/16928/26173018

분석

1. BFS를 통해 모든 칸의 최소 이동 수를 저장

코드

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

int n, m;
int map[110];
int dist[110];
int q[110];

void input() {
	scanf("%d%d",&n,&m);
	for (int i = 0; i < n + m; i++) {
		int s, e;
		scanf("%d %d",&s, &e);
		map[s] = e;
	}
}


int main() {
	//freopen("input.txt", "r", stdin);
	input();

	memset(dist, -1, sizeof(dist));
	q[0] = 1;
	dist[1] = 0;
	
	int front = 1;
	int rear = 0;

	while (true)
	{
		if (front == rear)break;

		int temp = q[rear];
		rear = rear + 1;

		for (int dice = 1; dice <= 6; dice++)
		{
			int nextNode = temp + dice;
			if (nextNode > 100) continue;

			if (map[nextNode] != 0) {
				nextNode = map[nextNode];
			}

			if (dist[nextNode] == -1) {
				dist[nextNode] = dist[temp] + 1;
				front++;
				q[front] = nextNode;
			}
		}
	}
	
	printf("%d",dist[100]);

	return 0;
}