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])
