[그래프] 백준 2206 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

import sys
from collections import deque

N,M = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
dy = [-1, 1, 0, 0]
dx = [0, 0, 1, -1]

def bfs():
    visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
    visited[0][0][1]=1
    q = deque()
    q.append((0,0,1))
    # 0 : 이미 부숨 -> 부술 수 없다.
    # 1 : 아직 안부숨 -> 부술 수 있다. 
    while q:
        cy, cx, cb = q.popleft()
        if cy==N-1 and cx==M-1:
            return visited[cy][cx][cb]
        for i in range(4):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0<=ny<N and 0<=nx<M:
                if graph[ny][nx]==0 and visited[ny][nx][cb]==0: # 처음방문 + 벽X
                    visited[ny][nx][cb]=visited[cy][cx][cb]+1
                    q.append((ny, nx, cb))
                elif graph[ny][nx]==1 and cb==1: # 벽 + 부술기회O (벽이면 무조건 부술 수 있어야하니까)
                    visited[ny][nx][0]=visited[cy][cx][cb]+1
                    q.append([ny, nx, 0])
    return -1
print(bfs())

코드는 전반적으로 이해가 간다.

조건문을 왜 저렇게 줬는지도 이해가 갔는데..

 

어떻게 저게 "최단 경로"라고 확신할 수 있을까?? 잠깐 이해가 안갔었는데

가장 처음 pop이 되는 경우라면, 가장 처음 queue에 push됐다고 생각할 수 있다.

가장 먼저 push됐다면 그만큼 빨리 접근됐다고 이해할 수 있으므로 최단 경로라고 확신할 수 있는 것이다.