16928번: 뱀과 사다리 게임

메모리

시간

1228 KB

0 ms

Code

#include <cstdio>
#include <queue>

using namespace std;

int main()
{
	int table[101] = {0,}; //사다리 혹은 뱀 경로를 저장할 배열
	int pin[101] = {0,}; // 위치에 따른 최소 횟수를 저장할 배열
	int n,m, start_pin, next_pin;
	queue <int> que; 
	scanf("%d%d", &n, &m);

	int key, value;
	for (int i = 1; i < (n + m + 1); i++)
	{
		scanf("%d%d",&key,&value);
		table[key] = value;
	}
	
	que.push(1);
	while (1)
	{
		start_pin = que.front();
		for (int i = 1; i < 7; i++)
		{
			next_pin = i + start_pin;
			if (table[next_pin] > 0)
				next_pin = table[next_pin];
			if (pin[next_pin] == 0)
			{
				pin[next_pin] = pin[start_pin] + 1;
				que.push(next_pin);
			}
			if (next_pin >= 94 && pin[100] == 0)
			{
				printf("%d", pin[next_pin] + 1);
				return 0;
			}
		}
		que.pop();
	}
	return 0;
}

문제 풀이

queue 를 사용하여 풀이해보았다.

삽질

처음에는 굳이 pin 배열을 선언하지 않고

queue<pair<int, int> > q;

큐 + pair 를 사용해서 두개의 값으로 주사위를 굴린 횟수까지 큐로 핸들해보려 했다.

하지만 해당 인덱스가 이전에도 나왔던 값인지에 대한 카운트를 또 해야했기에

pin 배열로 다시 풀이하였다,,,