Graphs: 286. Walls and Gates

286. Walls and Gates

 

from collections import deque
from typing import List

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        """
        문제 설명:
        -1: 벽 또는 장애물로 이동 불가능한 위치를 나타냄
         0: 게이트(문)가 있는 위치
        INF (2147483647): 빈 공간으로, 게이트까지의 거리를 계산해야 함
        목표:
        각 빈 공간(2147483647)을 가장 가까운 게이트까지의 거리로 업데이트
        도달할 수 없는 경우, INF를 그대로 유지
        해결 방법:
        - BFS(너비 우선 탐색)를 사용하여 게이트에서 시작해 거리를 계산
        - BFS는 최단 거리를 구하는 데 적합
        """
        ROWS, COLS = len(rooms), len(rooms[0])

        # 네 방향(상, 하, 좌, 우)을 나타냄
        # Four directions (up, down, left, right)
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

        # BFS 큐 초기화
        # Initialize a queue for BFS
        q = deque()

        # 모든 게이트를 큐에 추가
        # Add all gates to the queue
        for r in range(ROWS):
            for c in range(COLS):
                if rooms[r][c] == 0:  # 게이트 발견
                    q.append((r, c))

        # BFS로 최단 거리 계산
        # BFS for calculating the shortest distance
        nearest_dist = 1  # 시작 거리는 1로 초기화 / Start distance as 1

        while q:
            # 현재 큐에 있는 모든 노드 처리
            # Process all nodes currently in the queue
            for _ in range(len(q)):
                r, c = q.popleft()  # 큐에서 위치를 꺼냄 / Dequeue a position

                # 네 방향으로 이동
                # Move in four directions
                for dr, dc in directions:
                    R, C = r + dr, c + dc  # 새로운 위치 계산 / Calculate the new position

                    # 유효한 범위 내에 있으며, 빈 방(INF)인 경우만 처리
                    # Process only if within valid range and is an empty room (INF)
                    if R in range(ROWS) and C in range(COLS) and rooms[R][C] == 2147483647:
                        q.append((R, C))  # 새 위치를 큐에 추가 / Add the new position to the queue
                        rooms[R][C] = nearest_dist  # 거리를 업데이트 / Update the distance
            
            # 현재 레벨 탐색이 끝나면 거리를 증가
            # Increase the distance after processing the current level
            nearest_dist += 1