메모리
시간
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;
}
C++
복사
문제 풀이
queue 를 사용하여 풀이해보았다.
삽질
처음에는 굳이 pin 배열을 선언하지 않고
queue<pair<int, int> > q;
큐 + pair 를 사용해서 두개의 값으로 주사위를 굴린 횟수까지 큐로 핸들해보려 했다.
하지만 해당 인덱스가 이전에도 나왔던 값인지에 대한 카운트를 또 해야했기에
pin 배열로 다시 풀이하였다,,,
가장 적게 움직여서 갈 수 있는 수를 구하는 문제로 넓이우선탐색(BFS)의 특성상
가장 먼저 해당 인덱스에 저장 되는게 가장 적은 수가 된다.
그래서 도착지인 100에 주사위의 최대 수인 6을 뺀 94이상의 수가 나오면 해당 인덱스에 저장된 pin의 값 + 1을 하고 출력, 종료하였다.
