둔필승총

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

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

예제 입력 1 

3 3

011

111

110

예제 출력 1 

3

예제 입력 2 

4 2

0001

1000

예제 출력 2 

0

예제 입력 3 

6 6

001111

010000

001111

110001

011010

100010

예제 출력 3 

2

[문제 해설]

이 문제는 벽에 대한 것을 어떻게 해결해야될까가 고민이였다. 벽을 부수는 횟수를 최소한으로 해서 탈출을 해야 한다. 사실 벽을 부순다는 행위를 거리의 길이 즉 가중치라고 생각하면 된다. 그래서 거리가 짧은 곳으로 다녀 목적지까지 도달하게 해주는 다익스트라 알고리즘을 사용하면 된다. 다익스트라 알고리즘보다는 거의 BFS를 사용해서 푼 것 같다.

BFS대로 푸는데 최대한 벽이 없는 곳으로 가는 것이 유리하다. 벽이 없는 곳을 만났을 때는 큐에서 appendleft를 이용하여 먼저 가게 하고 벽이 있는 곳을 만나면 그냥 append를 통해 큐에 추가해준다. 

from collections import deque
m,n=map(int,input().split())
graph=[list(map(int,input())) for _ in range(n)]
bback=[[-1]*m for _ in range(n)]#가중치
dx=[-1,1,0,0]#상하좌우
dy=[0,0,-1,1]#상하좌우

q=deque()
q.append((0,0))
bback[0][0]=0
while q:
    x,y = q.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        if bback[nx][ny]==-1:
            if graph[nx][ny]==0:
                bback[nx][ny]=bback[x][y]
                q.appendleft((nx,ny))
            elif graph[nx][ny]==1:
                bback[nx][ny]=bback[x][y]+1
                q.append((nx,ny))
print(bback[n-1][m-1])