[BFS] 뱀과 사다리 게임

예제 입력 1

3 7

32 62

42 68

12 98

95 13

97 25

93 37

79 27

75 19

49 47

67 17

예제 출력 1

3

1. 5를 굴려 6으로 이동한다.
2. 6을 굴려 12로 이동한다. 이 곳은 98로 이동하는 사다리가 있기 때문에, 98로 이동한다.
3. 2를 굴려 100으로 이동한다.

예제 입력 2

4 9

8 52

6 80

26 42

2 72

51 19

39 11

37 29

81 3

59 5

79 23

53 7

43 33

77 21

예제 출력 2

5

1. 5를 굴려 6으로 이동하고, 사다리를 이용해 80으로 이동한다. 
2. 6을 굴려 86으로
3. 6을 또 굴려 92로
4. 6을 또 굴려 98로 이동하고
5. 2를 굴려 100으로 이동한다.

 

- 뱀이랑 사다리는 다음에 이동할 노드로써, 사실상 구분할 필요가 없음. 둘 다 동일하게 next[x] = y로 처리.

- 일반 노드는 뱀/사다리와 동일하게 처리하기 위해 next[x] = x;로 처리.

 

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

16928번: 뱀과 사다리 게임

#include <stdio.h>

const int MAX_SIZE = 101;
const int MAX_QUEUE_SIZE = 1000;

int N;
int M;

int dist[MAX_SIZE] = { 0, };
int next[MAX_SIZE] = { 0, };

class Queue
{
public:
	int front;
	int rear;

	int data[MAX_QUEUE_SIZE];

	Queue()
	{
		
	}

	void push(int item)
	{
		data[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	int pop()
	{
		int result = data[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty() { return front == rear; }
};
Queue q;

int main(void)
{
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= 100; i++)
	{
		dist[i] = -1;
		next[i] = i;
	}

	int inputMax = N + M;
	for (int i = 0; i < inputMax; i++)
	{
		int nowNode, nextNode;
		scanf("%d %d", &nowNode, &nextNode);

		next[nowNode] = nextNode;
	}

	dist[1] = 0;
	q.push(1);

	while (!q.isEmpty())
	{
		int nowNode = q.pop();

		for (int i = 1; i <= 6; i++)
		{
			if (nowNode + i > 100) continue;

			int nextNode = next[nowNode + i];

			if (dist[nextNode] == -1)
			{
				q.push(nextNode);
				dist[nextNode] = dist[nowNode] + 1;
			}
		}
	}

	printf("%d\n", dist[100]);

	return 0;
}