a-086-walls-and-gates2026-08-13mediumleetcode #286neetcode150

벽과 문

#array#breadth-first-search#matrix

문제

· problem

P.a-086-walls-and-gates

벽과 문

m×n 2D 격자가 주어집니다. 각 셀은 다음 중 하나입니다: - 0: 문(gate) - -1: 벽(wall) - 2147483647: 빈 방(empty room) 각 빈 방을 가장 가까운 문까지의 거리로 업데이트하세요. 문에 도달할 수 없는 셀은 그대로 2147483647로 유지됩니다. 격자를 제자리에서(in-place) 수정하세요.

제약

· m and n are in range [1, 100]
· rooms[i][j] is one of {-1, 0, 2147483647}
· There is at least one gate in rooms

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]

[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,2]]

example 2input → output

[[-1]]

[[-1]]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
0은 문(gate)을 나타내나요?
☐
-1은 벽으로, 통과할 수 없나요?
☐
원본 배열을 수정해야 하나요?
☐
각 방에 대해 개별적으로 BFS를 실행해야 하나요?
☐
문에 도달할 수 없는 방은 어떻게 처리하나요?
☐
벽을 먼저 처리한 후 방을 처리해야 하나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 격자 크기 초기화

○

ROWS, COLS = len(rooms), len(rooms[0])

○

ROWS, COLS = len(rooms), len(rooms)

○

ROWS = len(rooms) + 1
COLS = len(rooms[0]) + 1

step 2· 방문 추적 및 큐 초기화

○

visit = set()

○

visit = []
q = []

○

visited = set()
queue = deque()

step 3· 경계 및 벽 검증 헬퍼 함수

○

def addRooms(r, c):

○

def addRooms(r, c):
    if r < 0 or c < 0 or r >= ROWS or c >= COLS:
        return
    visit.add((r, c))
    q.append([r, c])

○

def addRooms(r, c):
    if (r, c) in visit or rooms[r][c] == -1:
        return
    visit.add((r, c))
    q.append([r, c])

step 4· 모든 문으로 BFS 초기화

○

for r in range(ROWS):

○

if rooms[r][c] != 0:
    q.append([r, c])
    visit.add((r, c))

○

if rooms[r][c] == 0:
    q.append([r, c])
    # 방문 여부 업데이트 없음

step 5· 거리별 층별 BFS 처리

○

while q:

○

while q:
    r, c = q.popleft()
    rooms[r][c] = dist
    dist += 1

○

while q:
    r, c = q.popleft()
    rooms[r][c] = dist
    addRooms(r + 1, c)
    addRooms(r - 1, c)
    addRooms(r, c + 1)
    addRooms(r, c - 1)

step 6· 4방향 인접 셀 탐색│ 중첩

○

addRooms(r + 1, c)

○

addRooms(r + 1, c)
addRooms(r, c + 1)

○

for dr, dc in [(1,0), (-1,0), (0,1), (0,-1), (1,1), (-1,-1)]:
    addRooms(r + dr, c + dc)

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

"""

    @param rooms: m x n 2D grid

    @return: nothing

"""

    def walls_and_gates(self, rooms: List[List[int]]):

        ROWS, COLS = len(rooms), len(rooms[0])

        visit = set()

        q = deque()

        def addRooms(r, c):

            if (

                min(r, c) < 0

                or r == ROWS

                or c == COLS

                or (r, c) in visit

                or rooms[r][c] == -1

):

                return

            visit.add((r, c))

            q.append([r, c])

        for r in range(ROWS):

            for c in range(COLS):

                if rooms[r][c] == 0:

                    q.append([r, c])

                    visit.add((r, c))

        dist = 0

        while q:

            for i in range(len(q)):

                r, c = q.popleft()

                rooms[r][c] = dist

                addRooms(r + 1, c)

                addRooms(r - 1, c)

                addRooms(r, c + 1)

                addRooms(r, c - 1)

            dist += 1

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]

→

[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,2]]

case 2

[[-1]]

→

[[-1]]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.