백준 2665 미로만들기

21.32

나의 답

import sys
from collections import deque
input = sys.stdin.readline
INF = sys.maxsize

n = int(input().rstrip())
maze = [list(map(int, list(input().rstrip()))) for _ in range(n)]
weights = [[INF] * n for _ in range(n)]
weights[0][0] = 0

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(node):
    q = deque([node])
    while q:
        p_x, p_y = q.popleft()
        for i in range(4):
            n_x = p_x + dx[i]
            n_y = p_y + dy[i]
            if (0 <= n_x < n) and (0 <= n_y < n):
                if weights[n_x][n_y] > weights[p_x][p_y]:
                    if not maze[n_x][n_y]: #벽이면
                        weights[n_x][n_y] = weights[p_x][p_y] + 1
                    else: #방이면
                        weights[n_x][n_y] = weights[p_x][p_y]
                    q.append((n_x, n_y))

bfs((0, 0))
print(weights[n-1][n-1])

단순한 BFS 문제였다.
단순한건 아닌가? 여튼 그냥 처음에 엄청 큰 값으로 해당 노드 방문하기 위한 비용 넣어놓고, 비용의 크고 작음을 비교해서 업데이트했다.