[백준] 1261. 알고스팟 (Python)

link 🔗 https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 

🔥 BFS

🔥 visit 배열에 벽을 부순 횟수를 기록하며 BFS를 돌린다.

🔥 벽을 부숴야 할 경우 +1, 벽을 부수지 않아도 되는 경우 현재 위치의 횟수를 그대로 가져가고, appendleft로 맨 앞에 넣어준다.

 

from collections import deque

X, Y = map(int, input().split())

board = [list(map(int, input())) for _ in range(Y)]
visit = [[0]*X for _ in range(Y)]

def BFS():
    q = deque()
    q.append((0, 0))
    visit[0][0] = 1
    dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        ny, nx = q.popleft()
        for i, j in dir:
            dy, dx = ny+i, nx+j
            if 0 <= dy < Y and 0 <= dx < X:
                if visit[dy][dx] == 0:
                    if board[dy][dx] == 0:
                        visit[dy][dx] = visit[ny][nx]
                        q.appendleft((dy, dx))
                    else:
                        visit[dy][dx] = visit[ny][nx]+1
                        q.append((dy, dx))

BFS()
print(visit[Y-1][X-1]-1)