2023.01.24 Today's Challenge

fabichoi 2023. 1. 24. 23:45

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

Snakes and Ladders - LeetCode

Snakes and Ladders - You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style [https://en.wikipedia.org/wiki/Boustrophedon] starting from the bottom left of the board (i.e. board[n - 1][0]) and alternati

leetcode.com

아예 감도 안잡힘 =_= 너무 오랫만에 풀어보려고 시도했음

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        board.reverse()

        for i in range(1, len(board), 2):
            board[i].reverse()
        
        ar = [None] + list(chain(*board))

        n, qu, seen, ct = len(ar) - 1, deque([1]), {1}, 0

        while qu:
            len_q = len(qu)

            for _ in range(len_q):
                cur = qu.popleft()
                if cur == n:
                    return ct
                
                for i in range(cur+1, min(cur+7, n+1)):
                    nxt = ar[i] if ar[i] + 1 else i

                    if nxt in seen:
                        continue
                    
                    seen.add(nxt)
                    qu.append(nxt)
            ct += 1

        return -1