[leetcode] 909. Snakes and Ladders

문제

909. Snakes and Ladders

이 문제는 풀어보길 추천!!!

분석

Constraints
1. 현재 속해있는 idx에서, 그 다음으로 갈 수 있는 idx는 (idx+1 ~ idx+6)까지이다.
2. 만일 현재 속해있는 idx의 board[idx]값이 -1이 아닌 다른 값이라면 ladder나 snake로 바아로 board[idx] 값으로 슝슝 이동한다.
3. idx = $n^2$ 가 되는 최소거리 구하기!
4. col, row가 해당하는 idx로 mapping되는 함수를 만들어 주어야한다.
5. 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.

• 최소거리 를 구하는 해당 제약 조건으로부터 DFS로 풀어야 한다는 것을 유추할 수 있다!

• 4번의 Constraint를 만족시키는 mapping함수를 짜는 것이 조금 까다로움! -> 이부분만 잘 해결되면 다른 부분은 다른 DFS와 푸는 방법이 비슷하다!

  
  

4번의 constraint를 만족시키는 번호판 생성하는 코드!

        idx_dict = {}
        cnt = 1
        row_count = 0
        # 번호판 생성!
        for i in range(n-1, -1, -1):
            if (row_count % 2 == 0):
                for j in range(0, n):
                    #numbers[i][j] = cnt
                    idx_dict[cnt] = (i, j)
                    cnt+=1
            else:
                for j in range(n-1, -1, -1):
                    # numbers[i][j] = cnt
                    idx_dict[cnt] = (i, j)
                    cnt+=1
            row_count+=1

BFS 최종 코드

from collections import deque
class Solution:
    def snakesAndLadders(self, board) -> int:
        n = len(board)
        visited = []
        queue = deque()
        
        numbers = [[0]* n for _ in range(n)]
        idx_dict = {}
        cnt = 1
        row_count = 0
        # 번호판 생성!
        for i in range(n-1, -1, -1):
            if (row_count % 2 == 0):
                for j in range(0, n):
                    #numbers[i][j] = cnt
                    idx_dict[cnt] = (i, j)
                    cnt+=1
            else:
                for j in range(n-1, -1, -1):
                    # numbers[i][j] = cnt
                    idx_dict[cnt] = (i, j)
                    cnt+=1
            row_count+=1
                
        start_v = (1, 0) # idx moves
        visited.append(1)
        queue.append(start_v)

        while queue:
            cur_idx, cur_dep= queue.popleft()
            cur_x, cur_y = idx_dict[cur_idx]
            #print("cur_idx: ", cur_idx, cur_dep)
            # 일단 cur_idx를 check
            if cur_idx == n**2:
                return cur_dep
            if cur_dep>=n**2 and cur_idx!=n**2:
                return -1
            
            min_step = cur_idx + 1
            max_step = min(cur_idx + 6, n**2)
            for next_i in range(min_step, max_step+1):
                next_x, next_y = idx_dict[next_i]
                if board[next_x][next_y] != -1: # 만약 ladder이나 snake를 타야한다면! 바로 그걸 타고 올라가기!
                    next_i = board[next_x][next_y] 
                    
                if next_i not in visited:   # 방문하지 않았다면
                    visited.append(next_i)
                    queue.append((next_i, cur_dep+1))  # 다음 방문할 곳에 넣는다!
        return -1

처음 시행착오 1: 5번 constraint를 잘못 이해함

            for next_i in range(min_step, max_step+1):
                next_x, next_y = idx_dict[next_i]
                ############## HERE #############
                if board[next_x][next_y] != -1: # 만약 ladder이나 snake를 타야한다면! 바로 그걸 타고 올라가기!
                    next_i = board[next_x][next_y] 
                    ##########################

• 해당 코드를 통해, ladder/snake를 이용할 시에는 한번에 슝슝타고 올라가서 move에 1번을 사용하게 됨.
• 따로 boolean값의 prev 변수를 두어 나는 이전 move에서 prev=True(ladder/snake를 타고 올라왔다면) 다시 ladder을 타지 않도록 하였음. --> 이게 문제!!! 왜냐하면 그 다음 move에서는 이미 ladder/snake를 타고 올라오지 않았기에 (ladder/snake를 타고 올라간게 이미 하나의 move로 계산되어지고 그 다음 move는 따로 올라온 것)

1. move+1을 통해 ladder/snake를 타고 올라가고 (prev=True)
2. +1 ~ +6사이에 올라가는 move를 하고 나서 ladder/snake를 타고 올라가는 것은 괜찮으나 이행동을 막은 것이나 다름없음
   
   

처음 시행착오 2: ending condition 잘못 적음

            cur_x, cur_y = idx_dict[cur_idx]
            # 일단 cur_idx를 check
            if cur_idx == n**2:
                return cur_dep
                ############## HERE #############

            elif  board[cur_x][cur_y] == n**2:
                return cur_dep+1
                #################################
                

• 지금의 cur_x, cur_y보다 아직 queue에 남아있는 x,y값들 중에서 더 빨리 n**2에 도달할 수 있는 경우의 수가 존재할 수 있기 때문에!!!!!!!!!!! exclusion이 생김

아래 예시 board를 통해 확인해볼 수 있음..!

board = [[-1,-1,-1,-1,-1,-1,-1,-1,206,286,-1,-1,-1,-1,-1,-1,-1,83,-1],[-1,-1,-1,-1,341,-1,-1,111,-1,-1,-1,-1,280,-1,-1,-1,-1,130,-1],[-1,-1,-1,-1,-1,-1,205,-1,-1,-1,-1,241,-1,-1,-1,-1,-1,-1,-1],[-1,273,304,17,-1,-1,-1,-1,-1,-1,232,-1,-1,-1,-1,-1,183,-1,-1],[-1,-1,133,-1,-1,-1,-1,-1,114,-1,-1,-1,145,-1,-1,256,-1,-1,-1],[351,-1,-1,38,315,-1,356,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,282],[346,-1,-1,-1,-1,-1,-1,-1,215,-1,-1,-1,40,-1,-1,347,109,-1,-1],[256,-1,-1,-1,127,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,227],[210,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,322,76,-1,-1,-1,94,185,40,-1,-1,-1,-1,-1,76,-1,-1,-1],[-1,-1,-1,-1,314,86,-1,-1,-1,326,-1,-1,-1,122,-1,-1,219,-1,219],[-1,83,202,210,-1,-1,-1,-1,-1,301,-1,-1,-1,-1,-1,-1,-1,136,-1],[-1,213,-1,-1,16,-1,122,-1,177,346,-1,348,1,-1,-1,-1,-1,-1,-1],[-1,360,-1,-1,-1,172,-1,266,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,76,319,302,-1,-1,361,-1,-1,-1,-1,144,-1,-1,-1,-1,-1,83,-1],[-1,258,-1,-1,286,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,357,83,64,-1,-1,-1,-1,7,-1,-1,-1,258,-1,-1],[-1,331,-1,-1,-1,-1,-1,-1,283,-1,244,278,-1,-1,-1,-1,-1,-1,-1],[-1,201,-1,-1,-1,-1,-1,-1,-1,-1,194,-1,-1,-1,-1,-1,-1,-1,-1]]

결과

if __name__ == "__main__":
    a = Solution()
    board = [[-1,-1],[-1,3]]
    print(a.snakesAndLadders(board) )

1