그래프와 순회. [16928]

[1. 문제 설명]

1번 칸에서 시작해서 주사위를 굴려 나온 수 만큼 이동 하여, 100번 칸에 도달 할 때,

주사위를 굴려야 하는 최소 횟수

(특정 칸에서는 사다리를 타고 앞쪽 칸 으로 이동하거나, 뱀을 타고 뒤쪽 칸으로 이동 할 수 있다.)

 

 

[2. 풀이 접근]

문제 상에서는 10x10 크기의 게임판이라는 표현이 있지만,

10x10 의 2차원 배열로 게임판을 모델링 할 필요는 없다.

 

사다리와 뱀에 대한 정보를 따로 취급 할 필요는 없다.

어차피 특정 칸으로 점프 하는 개념이기 때문이다.

 

bfs 로 풀어야 하는 이유(?)

일단 어떤 칸에서 +1, +2, ... +6 만큼 떨어진 위치로 이동하는데 필요한 비용은 모두 같다.(edge 에 별다른 weight 가 없다.)

특정 노드까지 최대한 빨리 도달해야 한다. (최단 경로?)

 

 

[3. 코드]