[BFS 문제] LEETCODE.909 Snakes and Ladders

문제풀이

이번 문제는 BFS 문제의 변형 유형이다. 일반 BFS 문제와의 차이점은 인접 Node 선택에 대해 2가지 변형을 이루고 있는 부분이다. 1. Map에 row별 reversed 처리를 통해 인접 Node 변형을 이룬다는 것이고 2. Ladder or snake를 통해 인접 Node에 대한 변형을 이룬다는 부분이다.
1. 주어진 board의 크기를 추출하여 snake or ladder를 관리하는 board 외에 실제 타겟 숫자를 관리하는 t_board를 생성한다.
2. queue를 정의한다. queue에는 (target number, col_index,row_index,distance)를 관리하도록 선언하였다.
3. BFS를 수행하게 된다.
- 큐가 빌때까지 popleft를 수행하면서 노드를 추출한다.
- 해당 노드 기준 인접 노드를 산출한다. ladder or snake가 존재하게 되면 board를 탐색하여 인접노드를 변형한다.
- 해당 노드를 popleft or append할때마다 visited에 node를 추가한다.
- target number를 찾게 되면 distance를 return한다.
- 큐가 빌때까지 target number를 찾지 못하면 접근이 불가능한 경우이므로 -1를 return한다.

코드

from collections import deque
from typing import List

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n_row = len(board[0])
        n = n_row * n_row
        t_board = []
        temp_bar = []
        len_val = 0
        isReversed = False
        dict_idx = {}
        ##1. 실제 target number를 관리하는 t_board 생성
        for i in range(n):
            len_val = len_val + 1
            temp_bar.append(i + 1)
            if len_val == n_row:
                if isReversed:
                    temp_bar.reverse()
                t_board.append(temp_bar)
                temp_bar = []
                len_val = 0
                isReversed = not isReversed
                
        t_board = t_board[::-1]
        ##2. target number에 대해 index 관리 변수 선언
        for i in range(n_row):
            for j in range(n_row):
                dict_idx[t_board[i][j]] = (i, j)
        
        #3. BFS 수행
        q = deque()
        q.append((1, n_row - 1, 0, 0))
        visited = {}
        visited[1] = True
        ans = 0
        
        while q:
            node = q.popleft()
            visited[node[0]] = True
            
            if node[0] == n:
                return node[3]
            
            distance = node[3] + 1
            
            for i in range(node[0] + 1, min(node[0] + 6, n) + 1):
                col, row = dict_idx[i][0], dict_idx[i][1]
                
                if board[col][row] != -1:
                    i = board[col][row]
                
                if i in visited:
                    continue
                
                q.append((i, dict_idx[i][0], dict_idx[i][1], distance))
                visited[i] = True
        
        return -1

Lookback

1. t_board를 생성하는 로직이 좀 지저분한 면이 있다. 하기와 같은 소스를 활용하면 동일한 코드 생성이 가능하다.
   t_board = []
   k = 1
   for i in range(len(board) - 1, -1, -1):
   t_board.append(board[i][::k])
   k *= -1

2. 인접 노드를 탐색하는 과정에서 visited에도 추가해줘야 불필요한 탐색을 방지할 수 있지만 이 부분을 놓쳤다. popleft시에만 업데이트하게 되면 큐에 노드를 넣고 popleft 하는 구간 내 탐색 과정에사 반복적으로 queue에 넣게되고 이로 인한 비효율이 발생한다. 큐에 넣는것이 결국 popleft할 것을 전제하기 때문에 미리 visited 업데이트 한다고 이해해도 직관적으로 이해될 듯하다.