LeetCode 909. Snakes and Ladders (python)

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.

 

 

 

 

#풀이

 

그래프 탐색을 통해서 최단거리를 구하는 문제이다. 다익스트라랑 bfs로 각각 한번씩 풀어봤다.

 

1. visit을 통해서 방문한 곳을 체크한다, (bfs 방문확인, dijkstra 이동횟수 체크)

2. 주사위로 1,2,3,4,5,6을 굴려서 이동한다 (bfs 방문했다면 pass , dijkstra 방문했어도, 이동횟수가 기록보다 적다면 이동)

3. 현재 위치가 마지막 위치 (n*n) 위치인지 확인한다.  -> 마지막 위치라면 return 

 

dijkstra는 heapq을 사용해 우선순위(이동횟수)를 두고 탐색하게 했다. 하지만 이 문제에서는 각각의 이동거리가 비슷하고 ,각각 선형으로 이동하는거리가 대부분 동일하게 1로 움직이기에 생각보다 탐색속도가 빠르지 않았다.

 

 

반대로 bfs는 넓이탐색을 통해서  이미 방문했던 곳이라면, 본인보다 이동횟수가 적은게 확실하기에 모든 이동경로를 1번 이상 방문하지 않기에 다익스트라보다 비교적 빠르게 탐색이 가능했다. 

Dijkstra

import heapq
import sys
INF = sys.maxsize
class Solution(object):
    def snakesAndLadders(self, board):
        n= len(board)
        line = [-1]
        flag = 1
        for y in range(n-1,-1,-1):
            if flag%2 ==1:
                for x in range(n):
                    line.append(board[y][x])
            else:
                for x in range(n-1,-1,-1):
                    line.append(board[y][x])
            flag+=1
        visit = [INF] *((n**2)+1)
        visit[1]=0
        q= []
        heapq.heappush(q,(0,1))
        while q:
            move,cur = heapq.heappop(q)
            for i in (1,2,3,4,5,6):
                next = cur+i
                if line[next]!= -1:
                    next = line[next]
                if next <(n**2) and visit[next]>move+1:
                    visit[next]=move+1
                    heapq.heappush(q,(move+1,next))
                    # print(move,next)
                if next == (n**2):
                    return move+1
        return -1

 

BFS

from collections import deque

class Solution(object):
    def snakesAndLadders(board):
        n= len(board)
        line = [-1]
        flag = 1
        for y in range(n-1,-1,-1):
            if flag%2 ==1:
                for x in range(n):
                    line.append(board[y][x])
            else:
                for x in range(n-1,-1,-1):
                    line.append(board[y][x])
            flag+=1
        print(line)
        visit =[0]*((n**2)+1)
        visit[1]=1
        q= deque()
        q.append((0,1))
        while q:
            move,cur = q.popleft()
            for i in (1,2,3,4,5,6):
                next = cur+i
                if line[next]!=-1:
                    next = line[next]
                if visit[next] ==0:
                    visit[next] = move+1
                    q.append((move+1,next))
                    print(next)
                if n**2 == next:
                    return move+1

        return -1


    
board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]

print(Solution.snakesAndLadders(board))

 

bfs는 방문 리스트를 통해 방문처리하게 되면 방문하지않는다,  반면 다익스트라는 방문을하고나서, 다음에 들어오는 방문인자가 횟수가 적다면 다시 방문처리를 한 후 이동을 하게된다,  dp의 배낭알고리즘과 다익스트라를 합쳐서 사용하면 속도 향상을 할 수 있지 않을까라는 생각을 해봤다.