909. Snakes and Ladders

909. Snakes and Ladders

 

https://youtu.be/6lH4nO3JfLk?si=VJAa2R-huRKNzl6O

 

문제 설명 요약

1. 게임 보드 구조:
   • n x n 크기의 정수 행렬 board가 있습니다.
   • board는 Boustrophedon 스타일로 채워져 있습니다:
     • 숫자는 아래 왼쪽에서 시작하여 첫 줄은 왼쪽 → 오른쪽으로 채워지고,
     • 다음 줄은 오른쪽 → 왼쪽으로 채워지는 식으로 반복됩니다.
   • 각 칸은 1부터 n2까지의 숫자로 라벨링됩니다.
2. 초기 상태:
   • 게임은 1번 칸(왼쪽 아래)에서 시작합니다.
3. 이동 규칙:
   • 매 턴마다 주사위를 굴려 1에서 6 사이의 값을 얻습니다.
   • 현재 칸 curr에서 [curr + 1, min(curr + 6, n^2)] 범위 내의 칸 중 하나로 이동합니다.
     • 예: 현재 칸이 10이면, 다음 칸은 11에서 16 사이입니다.
   • 이동한 칸에 사다리 또는 뱀이 있으면 해당 칸의 목적지로 즉시 이동합니다.
     • 예: 칸 12에 사다리가 있고, 사다리 목적지가 20이라면 20으로 이동.
4. 목표:
   • n2 번 칸(오른쪽 위)으로 이동하는 데 필요한 최소 주사위 굴림 횟수를 계산합니다.
   • 만약 n2 번 칸에 도달할 수 없다면 -1을 반환합니다.

from collections import deque
from typing import List

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        length = len(board)  # 보드의 크기(n x n)에서 n을 가져옴

        """
        board는 일반적으로 행렬 형태로 저장
        하지만 문제에서 언급된 Boustrophedon 스타일에서는:
            숫자가 아래쪽부터 시작하여 위로 올라가면서 채워지고,
            각 행에서 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 번갈아가며 채워짐

        일반 행렬의 형태:
        [   [36, 35, 34, 33, 32, 31],  # row 0
            [25, 26, 27, 28, 29, 30],  # row 1
            [24, 23, 22, 21, 20, 19],  # row 2
            [13, 14, 15, 16, 17, 18],  # row 3
            [12, 11, 10,  9,  8,  7],  # row 4
            [ 1,  2,  3,  4,  5,  6]]  # row 5

        board.reverse()를 통해 마지막 row가 가장 위로 오게 변환
        [   [ 1,  2,  3,  4,  5,  6],  # row 0
            [12, 11, 10,  9,  8,  7],  # row 1
            [13, 14, 15, 16, 17, 18],  # row 2
            [24, 23, 22, 21, 20, 19],  # row 3
            [25, 26, 27, 28, 29, 30],  # row 4
            [36, 35, 34, 33, 32, 31]]  # row 5        
        """
        board.reverse()  # Boustrophedon 스타일과 맞추기 위해 보드의 순서를 뒤집음

        def inToPos(square):            
            """
            Boustrophedon 스타일에서 주어진 숫자(square)를 행렬 좌표 [r, c]로 변환

            예를 들어:
            r
            5: 36 35 34 33 32 31
            4: 25 26 27 28 29 30
            3: 24 23 22 21 20 19
            2: 13 14 15 16 17 18 
            1: 12 11 10  9  8  7
            0:  1  2  3  4  5  6
            --------------------
            c   0  1  2  3  4  5

            square가 1부터 시작하므로 이를 0 기반 인덱스로 변환
            """
            r = (square-1) // length  # square가 몇 번째 행(r)에 있는지 계산
            c = (square-1) % length  # square가 몇 번째 열(c)에 있는지 계산

            if r % 2:  # r이 홀수(1, 3, ...)라면 오른쪽 -> 왼쪽 방향
                c = length - 1 - c  # 열의 순서를 반대로 변환

            return [r, c]  # 변환된 행렬 좌표 [r, c] 반환

        q = deque()  # BFS를 위한 큐 생성
        q.append([1, 0])  # 초기 상태: 시작 지점(square 1)과 이동 횟수(moves 0)
        visit = set()  # 방문한 칸을 기록하는 집합

        while q:  # BFS를 계속 수행
            square, moves = q.popleft()  # 현재 칸(square)과 이동 횟수(moves)를 가져옴

            for i in range(1, 7):  # 주사위를 던져 1부터 6까지 이동 시도
                nextSquare = square + i  # 주사위 값만큼 이동한 다음 칸 계산
                r, c = inToPos(nextSquare)  # 다음 칸의 행렬 좌표 계산

                if board[r][c] != -1:  # 사다리나 뱀이 있다면 목적지로 이동
                    nextSquare = board[r][c]

                if nextSquare == length * length:  # 마지막 칸에 도달하면 종료
                    return moves + 1  # 현재 이동 횟수에 1을 더해 반환

                if nextSquare not in visit:  # 방문하지 않은 칸이라면
                    visit.add(nextSquare)  # 방문 기록 추가
                    q.append([nextSquare, moves + 1])  # 큐에 다음 상태 추가

        return -1  # BFS를 종료했는데도 마지막 칸에 도달하지 못하면 -1 반환