[LeetCode 75] Medium - 1926. Nearest Exit from Entrance in Maze

1926. Nearest Exit from Entrance in Maze

 

# 최단거리 => BFS => queue

# 시작점을 que 에 넣고. pop 하면서 검색

# pop 할때마다. 4방향 검색: 1레벨 up

# 방문 셀 체크 해야함

 

 

https://youtu.be/fCfjOdi6V3g?si=RKIvqX7H_LOurZrM

 

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        # 최단거리 => buffer search => queue
        # 시작점을 que 에 넣고. pop 하면서 검색
        # pop 할때마다. 4방향 검색: 1레벨 up
        # 방문 셀 체크 해야함
        rows, cols = len(maze), len(maze[0])
        start = tuple(entrance)
        q = deque([start])
        res = 0
        visit = set([start])
        while q:
            for i in range(len(q)):
                r,c = q.popleft()
                # 현재 위치가 출구이면
                # - 입구가 아니고, [r,c] != entrance
                # - 출구(경계이므로, (r==0 or c==0 or r==rows-1 or c==cols-1) 이어야함) 이면
                if [r,c] != entrance and (r==0 or c==0 or r==rows-1 or c==cols-1):
                    return res
                for dr, dc in [(1,0),(-1,0), (0,1), (0,-1)]:
                    row,col = r+dr, c+dc
                    # 갈수 있는 영역이면
                    # - 미로 안에 있어야 하고: 0<=row<=rows-1 and 0<=col<=cols-1
                    # - 이동 가능한 영역 이면: "." (벽이 아님)
                    # - 방문 안한 포인트 여야 함: not in visit
                    if 0<=row<=rows-1 and 0<=col<=cols-1 and maze[row][col] == "." and (row, col) not in visit: 
                        q.append((row, col))
                        visit.add((row, col))
            res += 1
        return -1

 

GTP

from collections import deque

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        rows, cols = len(maze), len(maze[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 이동 방향: 오른쪽, 아래, 왼쪽, 위
        queue = deque([(entrance[0], entrance[1], 0)])  # (row, col, steps)

        # 시작점을 방문 처리
        maze[entrance[0]][entrance[1]] = '+'

        while queue:
            row, col, steps = queue.popleft()

            # 상하좌우로 이동
            for dr, dc in directions:
                nr, nc = row + dr, col + dc

                # 범위 확인 및 방문 여부 확인
                if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == '.':
                    # 출구 조건: 가장자리이면서 시작점이 아닌 경우
                    if nr == 0 or nr == rows - 1 or nc == 0 or nc == cols - 1:
                        return steps + 1

                    # 다음 탐색을 위해 큐에 추가하고 방문 처리
                    maze[nr][nc] = '+'
                    queue.append((nr, nc, steps + 1))

        return -1  # 출구를 찾지 못한 경우

 

내 최종 코드

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        mRows,nCols=len(maze), len(maze[0])
        visit = set([tuple(entrance)])  # 방문한 위치
        q = deque([(entrance[0], entrance[1], 0)]) # 시작점, 0번째 스텝

        direction = [(1,0),(-1,0),(0,1),(0,-1)]   # 4방향 이동

        while q:
            r, c, step = q.popleft()
            # 현재 위치가 출구이면.
            if (r==0 or r==mRows-1 or c==0 or c==nCols-1) and (r,c) != tuple(entrance):
                return step

	     # 4방향 탐색
            for dr, dc in direction:
                nr, nc = r+dr, c+dc
                if 0<=nr<mRows and 0<=nc<nCols and maze[nr][nc] == '.' and (nr,nc) not in visit:
                    q.append((nr,nc, step+1))
                    visit.add((nr,nc))  # 방문 처리

        return -1  # 출구를 찾지 못한 경우