[LeetCode] 909. Snakes and Ladders

- Problem

909. Snakes and Ladders

- 내 풀이 (BFS)

class Solution:
    def __init__(self):
        self.board: List[List[int]] = [[]]

    def bfs(self, start: int) -> int:
        N = len(self.board)
        moves = {start: 0}
        q = collections.deque([start])

        while q:
            curr = q.popleft()
            if curr == N**2:
                return moves[curr]

            for nxt in range(curr + 1, curr + 7):
                col, row = (nxt - 1) // N, (nxt - 1) % N
                y = ~col
                x = ~row if col % 2 else row

                if 0 <= col < N and 0 <= row < N:
                    if is_snake_or_ladder_block(self.board[y][x]):
                        nxt = self.board[y][x]

                    if nxt not in moves:
                        moves[nxt] = moves[curr] + 1
                        q.append(nxt)

        return -1

    def snakesAndLadders(self, board: List[List[int]]) -> int:
        self.board = board

        return self.bfs(1)

def is_snake_or_ladder_block(val: int) -> bool:
    BLANK = -1
    return val > BLANK

- 결과