LeetCode 1926(Nearest Exit from Entrance in Maze) 풀이

문제

첫번째 시도 (오답)

• 방식: BFS
• 시간복잡도: O(n * m)

문제를 보고 BFS라고 바로 생각할 수 있었습니다.

시작 노드부터 가까운 순으로 방문할 것이기 때문에 방문 노드가 출구라면 가차없이 반환하면 됩니다.

저는 시작 노드로부터의 거리를 저장하는 distance_map: List[List[int]]를 통해 최소 거리를 관리했습니다.

BFS로 돌면서 방문하지 않은 노드라면 최소거리를 업데이트하고 다음 방문 노드로 추가했습니다.

하지만 시간 초과 에러를 만났습니다.

제공받은 테스트케이스는 전부 통과했기 때문에 최적화를 고민하기로 합니다.

from collections import deque
class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        def isExit(target: tuple[int]):
            return maze[target[0]][target[1]] == '.' and (
                    (target[0] == 0 or target[0] == len(maze) - 1) or 
                    (target[1] == 0 or target[1] == len(maze[0]) - 1)
                ) and not (
                target[0] == entrance[0] and target[1] == entrance[1])

        def getAdjecent(target: tuple[int]):
            adj = [
                (target[0] + 1, target[1]),
                (target[0] - 1, target[1]),
                (target[0], target[1] + 1),
                (target[0], target[1] - 1)
            ]

            return list(
                filter(
                    lambda x:
                        x[0] >= 0 and
                        x[1] >= 0 and
                        x[0] < len(maze) and
                        x[1] < len(maze[0]) and
                        maze[x[0]][x[1]] == '.',
                    adj 
                )
            )

        distance_map = [[inf for _ in range(len(maze[0]))] for _ in range(len(maze))]

        distance_map[entrance[0]][entrance[1]] = 0

        will_visit = deque([(entrance[0], entrance[1])])
        visited = set()

        while will_visit:
            current_space = will_visit.popleft()

            distance = distance_map[current_space[0]][current_space[1]]

            for next in getAdjecent(current_space):
                if isExit(next):
                    return distance + 1
                if next not in visited:
                    distance_map[next[0]][next[1]] = distance + 1
                    will_visit.append(next)


            visited.add(current_space)

        return -1

두번째 시도 (정답)

일단 이 문제에서 미로의 너비는 최대 100 * 100입니다.

따라서 일반적으로 bfs를 한다면 크게 문제가 되지 않을 크기라고 판단했습니다.

그렇다면 어디선가 불필요하게 로직이 작동되고 있다는 의미로 판단했습니다.

원인은 방문한 노드를 또 방문할 수 있다는 점이었습니다.

방문 예정 노드로 등록하는 시점과 방문 완료로 등록하는 시점이 상이해서 불필요하게 방문 예정 노드가 많이 등록되었습니다.

이 문제를 해결하는 방법으로는 2가지였습니다.

• 방문 노드 확인 로직 추가
• 방문 예정 등록 시 검증

아래는 반영 코드입니다.

from collections import deque
class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        def isExit(target: tuple[int]):
            return maze[target[0]][target[1]] == '.' and (
                    (target[0] == 0 or target[0] == len(maze) - 1) or 
                    (target[1] == 0 or target[1] == len(maze[0]) - 1)
                ) and not (
                target[0] == entrance[0] and target[1] == entrance[1])

        def getAdjecent(target: tuple[int]):
            adj = [
                (target[0] + 1, target[1]),
                (target[0] - 1, target[1]),
                (target[0], target[1] + 1),
                (target[0], target[1] - 1)
            ]

            return list(
                filter(
                    lambda x:
                        x[0] >= 0 and
                        x[1] >= 0 and
                        x[0] < len(maze) and
                        x[1] < len(maze[0]) and
                        maze[x[0]][x[1]] == '.',
                    adj 
                )
            )

        distance_map = [[inf for _ in range(len(maze[0]))] for _ in range(len(maze))]

        distance_map[entrance[0]][entrance[1]] = 0

        will_visit = deque([(entrance[0], entrance[1])])
        visited = set()

        while will_visit:
            current_space = will_visit.popleft()

            distance = distance_map[current_space[0]][current_space[1]]

            for next in getAdjecent(current_space):
                if isExit(next):
                    return distance + 1
                if next not in visited:
                    if distance_map[next[0]][next[1]]> distance + 1:
                        distance_map[next[0]][next[1]] = distance + 1
                        will_visit.append(next)


            visited.add(current_space)

        return -1

느낀 점

저는 모서리에서만 출발할 수 있다고 생각했습니다.

문제에 버젓이 중간부터 시작한다는 힌트가 나와있는데 말이죠.

종종 이런 식으로 시간을 낭비하는 경우가 있습니다.

항상 느끼지만 문제를 잘 읽어야 할 것 같습니다.

문제는 bfs로 풀어야겠다고 어렵지 않게 느꼈지만, 최적화 방법을 고민해야 했기에 좋은 경험이었습니다.

 

 

Nearest Exit from Entrance in Maze - LeetCode