BOJ 1261 알고스팟

https://www.acmicpc.net/problem/1261
시간 1초, 메모리 128MB
input :

• 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)
• 0은 빈 방을 의미하고, 1은 벽을 의미
• (1, 1)과 (N, M)은 항상 뚫려

output :

• 최소 몇 개 부수어야 하는지 출력

조건 :

• 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방

bfs 문제 다익스트라인진 몰랐는데 그냥 품.. 벽을 최소한 깨야 하는 거니까 뭐 맞겠지..

새삼 해야하는 예외처린 별로 없다.
맨날 continue 걸어줄 때
nx > n, ny > m 이라고 해서 에러가 난다.
= 까지 포함해 주어야 그래프 밖으로 나가는 것을 막을 수 있다.

함수의 동작은 다음 이동하려는 지점에 벽이 존재하는지, 안 하는지.
그 지점을 이미 간적이 없거나
visit[x][y] + 1 이번에 벽이 존재해서 뚫은 횟수를 더한것이
visit[nx][ny]의 값보다 작다면 q에 append 해주자.

벽이 없을 때에도 위의 방법을 반복하자.

import sys
from _collections import deque

m, n = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().strip())))
visit = [[99999] * m for i in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


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

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= n or nx < 0 or ny >= m or ny < 0:
                continue
            # 다음 이동하는 곳에 벽이 존재.
            if graph[nx][ny] == 1:
                if visit[nx][ny] == 99999 or visit[nx][ny] > visit[x][y] + 1:
                    visit[nx][ny] = visit[x][y] + 1
                    q.append((nx, ny))
            else:
                if visit[nx][ny] == 99999 or visit[nx][ny] > visit[x][y]:
                    visit[nx][ny] = min(visit[nx][ny], visit[x][y])
                    q. append((nx, ny))

bfs()
print(visit[n - 1][m - 1])