Leetcode 505. The Maze II

문제

There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). 
The ball can go through the empty spaces by rolling up, down, left or right, 
but it won't stop rolling until hitting a wall. 
When the ball stops, it could choose the next direction.

Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], 
return the shortest distance for the ball to stop at the destination. 
If the ball cannot stop at destination, return -1.

The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).

You may assume that the borders of the maze are all walls (see examples).

서론

• 빈 공간은 0, 벽은 1로 이루어진 미로가 있다.
• 공은 빈 공간을 따라 위, 아래, 왼쪽, 오른쪽으로 이동할수 있으나 벽에 부딫히기 전까지 멈추지 않는다.
• 공이 멈추면 다음 방향으로 이동할수 있다.

본론

• m * n 미로에 대해 공의 시작점과 목표지점이 주어진다.
• 공이 이동하여 목표지점까지 도달할때 이동하는 최소 거리를 구하시오
• 만약 목표지점에 공이 멈출수 없다면 -1을 리턴하시오

조건

• 배열의 border 부분은 벽이라고 가정한다.

---

예시

• 왼쪽 -> 아래 -> 왼쪽 -> 아래 -> 오른쪽 -> 아래 -> 오른쪽 으로 이동시 12칸에 도달 가능하다.

---

제한

• $m == maze.length$
• $n == maze[i].length$
• $1 <= m, n <= 100$
• maze 배열은 0 혹은 1로 이루어짐
• $start.length == 2$
• $destination.length == 2$
• $0 <= startrow, destinationrow < m$
• $0 <= startcol, destinationcol < n$
• 시작지점과 목표지점은 둘다 maze에서 0이다.

---

풀이

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        shortest = defaultdict(lambda: float('inf'))

        ROW = len(maze)
        COL = len(maze[0])

        def bound_check(r: int, c: int) -> bool:
            if 0 <= r < ROW and 0 <= c < COL and maze[r][c] == 0:
                return True

            return False

        directions = [
            [-1, 0], [1, 0], [0, -1], [0, 1]
        ]

        q = deque([(start[0], start[1], 0)])
        shortest[(start[0], start[1])] = 0

        while q:
            r, c, distance = q.popleft()

            for tr, tc in directions:
                cr, cc = r, c
                dist = 0

                while bound_check(cr + tr, cc + tc):
                    cr += tr
                    cc += tc
                    dist += 1

                if shortest[(cr, cc)] > distance + dist:
                    shortest[(cr, cc)] = distance + dist
                    q.append((cr, cc, distance + dist))

        val = shortest[(destination[0], destination[1])]

        return val if val != float('inf') else -1

• 평범하게 bfs를 통해 시작지점에서 탐색을 하되, check를 쓰지 않고 해당 지점에 가기까지 쓰인 최소 거리를 shortest로 관리해서
• shortest가 새로운 작은 값으로 바뀔때, 즉 해당 지점으로 가는 새로운 빠른 방식이 있을때에만 그 지점으로부터 탐색을 하도록 한다.
• 일반적인 BFS에서 최소한만 변경

---

후기

• 여기서 최적화를 더 해야 할 줄 알았는데 생각보다 속도도 빠르고 ( 60ms ) 괜찮아서 멈췄다.
• 이럴거면 진즉에 풀걸 ㅋㅋㅋ 괜히 쫄아서