[백준 16928]뱀과 사다리 게임

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

1)문제분류

-BFS

-다익스트라

2)문제해결

Move[index]: index에사다리,또는 뱀의 위치를 표시, 하고 value에 이동할 위치를 넣어준다.

chk[]:int형 선언을 통해 주사위 굴린 횟수를 최솟값으로 갱신한다.

(bool형으로 하면 애매한 이유가, 주사위 굴릴 경우에만 굴린 횟수 증가, 사다리나 뱀을 만나 이동할땐느 굴린횟수가 증가 되지 않기 때문.

->굴린횟수 최솟값을 구해야하기 때문)

#include<iostream>

#include<queue>

using namespace std;

int Move[102];

int map[102];

int chk[102];

typedef struct P

{

int x, cnt;

}P;

int n, m;

queue<P>pq;

void BFS()

{

chk[1] = true;

pq.push({ 1,0 });

while (!pq.empty())

{

P output = pq.front();

pq.pop();

if(Move[output.x] > 0) //사다리나 뱀이 있다면 

{

if (chk[Move[output.x]] > output.cnt )

    {

chk[Move[output.x]] = output.cnt;

    pq.push({ Move[output.x],output.cnt});

    }

}

else  //사다리나 뱀이 없다면 

{

for (int i = 1; i <= 6; i++) // 주사위굴리기 

{

if (1 <= output.x + i && output.x + i <= 100 && chk[output.x + i]>output.cnt+1)

{

chk[output.x + i] = output.cnt+1;

pq.push({ output.x + i,output.cnt + 1 });

}

}

}

}

return;

}

int main()

{

for (int i = 0; i <= 100; i++)

{

chk[i] = 98765432;

}

cin >> n >> m;

int u, v;

for (int i = 0; i < n+m; i++)

{

cin >> u >>v;

Move[u] = v;   //u->v로 이동 

}

BFS();

cout << chk[100] << endl;

}