난이도 : level 2
유형 : 격자 BFS
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/1844

---

전형적인 격자 BFS 최단거리 문제이다.

1은 이동 가능, 0은 벽. 시작은 (0,0), 도착은 (n-1,m-1)이고, 상하좌우만 이동 가능하다.
핵심은 큐로 BFS 하면서 방문과 거리(dist)를 동시에 관리하는 것이다.

해답 및 풀이

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0]) # n : 세로 길이, m : 가로 길이

    # 방문 겸 최단거리 기록 배열 (미방문 = -1)
    dist = [[-1] * m for _ in range(n)]
    dist[0][0] = 1 # 시작 칸도 칸수에 포함되므로 1로 초기화.

    # 방향벡터 배열
    dy = (-1,1,0,0)
    dx = (0,0,-1,1)

    q = deque()
    q.append((0,0))

    while q:
        y, x = q.popleft()

        # 도착 지점에 도달하면 바로 반환
        if y == n-1 and x == m-1:
            return dist[y][x]
        
        for k in range(4):
            ny, nx = y + dy[k], x + dx[k]

            # 범위 체크
            if ny < 0 or ny >= n or nx < 0 or nx >= m:
                continue
            # 벽이거나 이미 방문했다면 패스
            if maps[ny][nx] == 0 or dist[ny][nx] != -1:
                continue

            # 처음 방문 => 최단거리 갱신 후 큐에 추가
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))
    
    # 도달 불가능
    return -1

이런 격자 BFS 문제의 핵심

1. 큐에 좌표를 넣고, 방문 배열로 관리한다.

일반 그래프에서는 visited[node] 로 관리했지만

격자에서는 좌표 (y, x) 기준으로 관리해야 해서 visited[y][x] 나 dist[y][x] 식으로 만든다.

2. 상하좌우 탐색 (dx,dy) 패턴

이건 거의 공식처럼 외우면 편하다.

dy = (-1,1,0,0)
dx = (1,-1,0,0)

3. BFS 는 처음 도착한게 무조건 최단거리.
   즉 dist[ny][nx] = dist[y][x] + 1 갱신 처리

4. 초기 세팅 잘하기
   시작점 (0,0) dist[0][0]=1 이나 큐에 시작점 잘 넣기.

5. 도달불가 처리
   프로그래머스에서는 조기종료 & return 도달불가처리 해주는 편

---

추가로 좌표에서는 (x,y) 가로 세로 가 익숙하지만
프로그래밍 좌표(배열) 에서는 (y,x) 이다. (행, 열)