[LeetCode/BFS] 909. Snakes and Ladders (medium, python)

https://leetcode.com/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

LeetCode - The World's Leading Online Programming Learning Platform

아이디어

BFS로 가장 짧은 이동 시간을 구하면 됐다.

2차원 리스트 보드판을 1차원으로 바꿔서 풀었다.

새 보드판 생성

주어진 board는 아래와 같은 형식이다

16	15	14	13
9	10	11	12
8	7	6	5
1	2	3	4

이러면 bfs에서 이동을 처리할때 복잡할 것 같아서 아래와 같은 일차원 리스트로 바꿨다. (이동하는 방향이 정해져있어서 가능하다.)

1

2

3

4

5

6

7

8

9

...

    N = len(board)

    b = []
    for i in range(N - 1, -1, -1):
        if N % 2 == 0:
            if i % 2 == 0: b += board[i][::-1]
            else: b += board[i]
        else:
            if i % 2 == 1: b += board[i][::-1]
            else: b += board[i]

N*N 보드판에서 N의 크기가 짝수일 때와 홀수일 때 도착하는 곳이 다르기 때문에 나누어서 구해주었다.

 

이동 구현

    visited = [0] * (N * N)
    queue = deque([(0, 0)])
    while queue:
        print(queue)
        x, m = queue.popleft()
        
        if x == (N * N - 1):
            return m
        
        for i in range(1, 7):
            nx = x + i
            if nx < 0 or nx >= N * N or visited[nx] == 1: continue
            visited[nx] = 1

            if b[nx] > -1:
                queue.append((b[nx] - 1, m + 1)) 
            else:
                queue.append((nx, m + 1))

    return -1

문제 조건 중에 연달아서 뱀이나 사다리로 이동하지는 못한다는 것이 있다. 

그래서 뱀이나 사다리로 이동해서 도달한 위치의 visited는 변경하지 않고, 이동한 곳에서 무조건 1칸은 움직이게 구현하였다.

전체 코드

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        N = len(board)

        b = []
        for i in range(N - 1, -1, -1):
            if N % 2 == 0:
                if i % 2 == 0: b += board[i][::-1]
                else: b += board[i]
            else:
                if i % 2 == 1: b += board[i][::-1]
                else: b += board[i]

        visited = [0] * (N * N)
        
        queue = deque([(0, 0)])
        while queue:
            x, m = queue.popleft()
            if x == (N * N - 1):
                return m
            
            for i in range(1, 7):
                nx = x + i
                if nx < 0 or nx >= N * N or visited[nx] == 1: continue
                visited[nx] = 1

                if b[nx] > -1:
                    queue.append((b[nx] - 1, m + 1)) 
                else:
                    queue.append((nx, m + 1))

        return -1