뱀과 사다리 게임

나의 논리

‘주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?’
주사위를 몇번 굴려야하는지 묻는 문제이다. 주사위를 한 노드에서 다른 노드로 이동 할때에는 그 거리가 1이기 때문에 ( 주사위를 1번 굴려야함) A <->B의 노드 거리는 1이고 최소거리를 구하는 문제이므로
BFS로 풀수있다.

큐에서 하나의 노드를 pop 한 뒤, 그 점이 사다리 또는 뱀이라면 좌표를 이동 시킨 후, 이동 시킨 좌표에서 주사위를 던져야한다. 주사위를 던져 이동시킨 좌표가 nx라고 한다면
nx를 처음 방문하는 경우, 지금 상태에서 nx를 방문한것이 기존에 방문한것보다 빠르다면 방문한다. 그렇지 않다면 nx에 갱신되는 거리값과 nx 이후로 갱신되는 거리는 기존보다 크기 때문에 최솟값을 구하는 연산에서 의미가 없으므로 방문하지 않는다.