[LeetCode] 909. Snakes and Ladders [도전중]

LeetCode - The World's Leading Online Programming Learning Platform

뱀과 사다리가있는 Board가 주어집니다.

출발지는 왼쪽 최하단이고 목적지는 n*2입니다.

 

n*2에 도달하는데 필요한 최소이동수를 반환합니다.

만약 n*2에 도달할 수 없다면 -1을 반환합니다.  

 

 

Example 1:

Input: board = [
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]
]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1

 

문제 접근

최단경로를 반환하는 문제입니다.

BFS를 통해 탐색하여 가장 빨리 도착지를 찾아 결과를 return해야겠다고 생각했습니다.