909. Snakes and Ladders

문제설명

영어문제를 번역하면 아래와 같다.

문제는 n x n 크기의 정수 행렬(board)이 주어지며, 이 행렬의 각 칸은 Boustrophedon 스타일로 라벨이 붙어 있습니다. 라벨링은 보드의 왼쪽 아래에서 시작하여 시작하며, 각 행은 번갈아 가면서 라벨이 매겨집니다.

위의 부분 때문에 조금 헤맸다. 숫자가 아래왼쪽부터 지그재그로 붙어있기 때문에 주의해야 한다.

보드판은 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]] 이렇게 -1또는 점프해야 하는(사다리 or 뱀이라고 표현됨) 숫자가 되어있으니 가야하는 숫자만 헷갈리지 않으면 된다.

보통 보드판 bfs문제는 인덱스를 설정해서 상,하,좌,우로 움직이지만, 이 문제는 숫자를 기준으로 움직이고, 숫자로 인덱스를 추정해서 움직인다.
현재 숫자가 curr이라고 하고, 주사위까지 던져서 임의로 1~6을 더하며 움직이는 범위를 옮긴다.
아래 문제설명을 보면 무슨 말인지 이해가 갈 수 있다.

당신은 보드의 첫 번째 칸(1번 칸)에서 게임을 시작합니다. 각 이동에서는 현재 위치한 칸(curr)에서 다음을 수행합니다:
범위 [curr + 1, min(curr + 6, n^2)] 내에서 라벨이 있는 목적지 칸(next)을 선택합니다. 이 선택은 표준 6면체 주사위 굴리기의 결과를 시뮬레이션하는 것으로, 보드의 크기에 관계없이 항상 최대 6개의 목적지가 있습니다.
만약 next 칸에 뱀이나 사다리가 있으면, 해당 뱀이나 사다리의 목적지로 이동해야 합니다. 그렇지 않으면 next 칸으로 이동합니다.
게임은 n^2번 칸에 도달하면 종료됩니다.
행 r과 열 c에 있는 보드 칸이 뱀이나 사다리를 가지고 있다면, board[r][c] != -1입니다. 이 경우, 뱀이나 사다리의 목적지는 board[r][c]입니다. 단, 1번 칸과 n^2번 칸에는 뱀이나 사다리가 시작되지 않습니다.
주의할 점은, 이동할 때 뱀이나 사다리의 목적지로만 한 번 이동하며, 뱀이나 사다리가 다른 뱀이나 사다리의 시작점일 경우 연속해서 이동하지 않습니다.

그래서 문제의 답은 최소 몇번 이동 해야 하냐? 이다

최소 몇 번의 이동으로 n^2번 칸에 도달할 수 있는지 반환하세요. 만약 n^2번 칸에 도달할 수 없는 경우, -1을 반환하세요.

문제 해결 코드

나는 인덱스를 물고 넘어지다가 결국 안되서 외쿡 피플의 답을 보고 해결했다.

from collections import deque
class Solution(object):

    def getPos(self, pos, n):
        row = (pos - 1) // n
        col = (pos - 1) % n
        if row % 2 == 1: #홀수 행은 열의 순서가 거꾸로 됨
            col = n - 1 - col
        row = n - 1 - row
        return row, col

    def snakesAndLadders(self, board):
        n = len(board)
        visited = set()
        queue = deque([(1,0)]) #(position == 숫자, moves)
        while queue:
            pos, moves = queue.popleft()
            for i in range(1,7):
                newPos = pos + i
                if newPos > n*n:
                    break
                r, c = self.getPos(newPos, n)
                if board[r][c] != -1: #사다리 or 뱀
                    newPos = board[r][c] #새로운 자리로 간다
                if newPos == n * n: #답 찾음
                    return moves + 1
                if newPos not in visited:
                    visited.add((newPos))
                    queue.append((newPos, moves+1))
        return -1