1261: 알고스팟

• visit이라는 이름의 미로와 같은 크기의 2차원 list를 통해 부수어야하는 벽의 최소 개수를 저장해놓음

import sys
from collections import deque

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

def bfs():
    queue = deque([]); queue.append((0, 0))
    visit[0][0] = 0

    while queue:
        curr = queue.popleft()

        if curr[0] == N-1 and curr[1] == M-1:
            print(visit[N-1][M-1])
            return
        
        for i in range(4):
            nx = curr[0] + dx[i]; ny = curr[1] + dy[i]

            if 0 <= nx <= N-1 and 0 <= ny <= M-1 and visit[nx][ny] == -1:
                if Map[nx][ny] == 1:
                    visit[nx][ny] = visit[curr[0]][curr[1]] + 1
                    queue.append((nx, ny))
                else:
                    visit[nx][ny] = visit[curr[0]][curr[1]]
                    queue.appendleft((nx, ny))


M, N = map(int, input().split(' '))

Map = []
for n in range(N):
    Map.append(list(map(int, list(sys.stdin.readline()[:-1]))))

visit = [[-1] * M for _ in range(N)]
bfs()

• visit list의 값들을 -1로 초기화
• visit[x][y] == -1 일 때 queue에 (nx, ny)를 append
• • (nx, ny)가 벽이라면, 즉 Map[nx][ny] == 1이라면
    -> visit[nx][ny] = visit[x][y] + 1로 갱신
    -> queue.append((nx, ny))
• • (nx, ny)가 벽이 아니라면, 즉 Map[nx][ny] == 0이라면
    -> visit[nx][ny] = visit[x][y]로 갱신
    -> queue.appendleft((nx, ny))을 해줌으로써 최소 개수에 우선 순위를 부여해줌