[알고리즘/백준] 1261번 : 알고스팟(python)

bfs문제이다.
0 or 1의 가중치를 가지고 있기 때문에 0-1bfs를 이용하여 풀면 된다.

왜 -1로 만들어야 하는지 이해가 가지 않았는데 디버깅을 해보니 가중치가 0 or 1이기 때문에 계속 0이 나오게 된다. 그래서 -1로 만들어 주었다.

from collections import deque


def bfs(x, y):
    q = deque()
    q.append([0, 0])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if ans[nx][ny] == -1:
                    if a[nx][ny] == 0:
                        ans[nx][ny] = ans[x][y]
                        q.appendleft([nx, ny])
                    else:
                        ans[nx][ny] = ans[x][y] + 1
                        q.append([nx, ny])


N, M = map(int, input().split())
a = [list(map(int, input())) for _ in range(M)]
ans = [[-1] * N for _ in range(M)]
ans[0][0] = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
bfs(0, 0)
print(ans[M - 1][N - 1])