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 starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
The game ends when you reach the square n2.
A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.
Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1.

풀이

• 주어진 2D 배열 board를 1D 배열로 변환한다.
  • 짝수라면 그대로, 홀수라면 reverse
• bfs 탐색할 큐와 visited 변수를 생성한다.
  • q: (현재위치, 현재까지 이동한 횟수)를 저장한다.
  • visited: 방문했던 위치를 저장한다.
• while 문을 돌면서 maps[now]가 -1이 아닌 칸을 만나면 now = maps[now]로 갱신한다.(사다리 or 뱀 칸인 경우)
• now == n * n 이라면 끝에 도착했으므로 return cnt
• for문을 now + 1부터 min(now + 6, n * n) + 1까지 돈다.
  • min(now + 6, n * n)의 의미는 마지막 칸의 수가 36이고 현재 칸이 34일 때, 36을 넘을 수 없다는 뜻이다.
  • 아직 방문하지 않은 칸이라면 방문처리를 해주고 q에 다음 위치와 횟수 + 1을 추가한다.
• while문 안의 return문을 만나지 못하고 q가 비게 된다면 return -1 만나 도달할 수 없음을 나타낼 수 있다.

Solution(Runtime: 104ms)

from collections import deque


class Solution:
    def to_1d(self, n, board):
        result = [0]
        for i, row in enumerate(board[::-1]):
            if i % 2:
                result.extend(row[::-1])
            else:
                result.extend(row)
        return result

    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        q = deque([(1, 0)])
        visited = set()
        maps = self.to_1d(n, board)

        while q:
            now, step = q.popleft()
            if maps[now] != -1:
                now = maps[now]
            if now == n * n:
                return step
            
            for next_dice in range(now + 1, min(now + 6, n * n) + 1):
                if next_dice not in visited:
                    visited.add(next_dice)
                    q.append((next_dice, step + 1)) 

        return -1    

다른 사람은 1차원 배열로 변환하지 않고 아래와 같은 함수를 써서 row, col 값을 가져오도록 했다. 이때도 ㄹ 모양처럼 서로 번갈아가면서 진행되므로 짝수인 경우와 홀수인 경우를 나눠서 처리했다.

def label_to_position(label):  # label: 현재 위치
    r, c = divmod(label - 1, n) # 현재 위치를 n으로 나누어 r, c 값을 구한다
        if r % 2 == 0:  # 짝수 열이라면 
            return n - 1 - r, c
        return n - 1 - r, n - 1 - c  # 홀수 열이라면