Daily LeetCode Challenge - 909. Snakes and Ladders

Problem From.

https://leetcode.com/problems/snakes-and-ladders/

오늘 문제는 사다리와 뱀이 있는 주사위 게임 말판에서 목적지에 도착할 수 있는 가장 최소의 주사위 굴리는 수를 반환하는 문제였다.

이 문제는 BFS 로 풀 수 있었다.
먼저 이차원배열로 되어있는 말판을 일차원배열로 바꾸어서 BFS 를 활용하기 편하게 만들고,
visit 배열과 queue 에는 현재 위치와 움직인 수가 들어있는 move 를 Pair 로 짝지어서 넣어서 각 움직임마다 move 가 함께 기록되도록 하였다.

class Solution {
    fun snakesAndLadders(board: Array<IntArray>): Int {
        
        val total = Math.pow(((board.size).toDouble()), 2.0).toInt()
        val modBoard = IntArray(total) { 0 }
        
        var cnt = 0
        var inc = true
        for(i in board.size - 1 downTo 0) {
            if(inc){  
                for(j in 0 until board.size) {
                    modBoard[cnt] = board[i][j]
                    cnt += 1
                }
                inc = false
            }else {
                for(j in board.size - 1 downTo 0) {
                    modBoard[cnt] = board[i][j]
                    cnt += 1
                }
                inc = true
            }
        }
        
        val visit = BooleanArray(total){ false }
        val queue : Queue<Pair<Int, Int>> = LinkedList()
        var move = 0
        
        queue.add(Pair(0, 0))
        
        while(queue.isNotEmpty()) {
            val curr = queue.poll()
            var currPos = curr.first
            val currMove = curr.second
            
            if(visit[currPos]) continue
            visit[currPos] = true
            if(currPos == total - 1) return currMove
            
            val maxMove = Math.min(currPos + 6, total - 1)
            for(i in currPos + 1 .. maxMove) {
                
                val next = if(modBoard[i] != -1) modBoard[i] - 1 else i
                
                queue.add(Pair(next, currMove + 1))
            }
            
        }
        
        return -1
        
    }
}

위 풀이의 시간 복잡도는 O(N^2) 가 된다.