백준 16928번 뱀과 사다리 게임 C++

 

1. 문제설명

10 x 10 보드판맵이 있고, 해당 보드판은 1 ~ 100까지 수가 순서대로 적혀있다.

플레이어는 주사위를 굴려 나온 수 만큼 이동이 가능한데

플레이어가 i번째 칸에 있고, 주사위의 수가 4라면 i + 4만큼 이동해야 한다.

만약 주사위를 굴린 결과가 100을 넘어가면 이동이 불가능하다.

도착한 칸이 사다리라면, 사다리를 타고 위로 올라가고

뱀이 있는 칸에 도착하면, 뱀을 따라 내려가게 된다.

게임의 목표는 1번 칸에 시작해 100번째 칸에 도착하는 것이다.

주사위를 조작할 수 있다고 하였을때, 100번째에 도착하기 위해 굴려야 하는 주사위 횟수를 구하는 문제이다.

 

따로 방향키가 필요 없이 주사위의 수를 더하며 이동하면 되기 때문에

한줄 배열로 101칸 짜리를 만들어준다, 1 ~100 숫자를 순서대로 넣었을때 보기 편하기 위해  

 

다음 사다리와 뱀의 정보를 받아 해당 move벡터에 넣어준다.

 

그다음 현재 칸에 도착하기 위한 주사위 횟수를 저장해줄 dist 벡터를 만들어준다.

queue를 만들어 dist의 첫번째 값을 push하며 시작한다. 1번부터 시작

 

q가 빌때까지 반복하며 주사위의 숫자 6칸을 bfs를 통해 너비탐색으로 100을 넘어가지 않는 값을 한정지어 검사하며 이동한다.

모든 큐가 비어지면 탐색종료로 dist[100]을 출력하면 100까지 가기위한 주사위의 횟수가 나오게 된다.