[백준1261번] 알고스팟 / Python3

문제

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

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (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를 활용하여 푸는 문제로 방문 여부 대신 visited 배열에 해당 위치까지의 벽을 뿌순 수의 최솟값을 저장하여 BFS로 탐색을 하였다. 따라서 잔지 방문 여부를 True와 False로 구분하는 것이 아니고 다음 위치의 벽을 부순 값이 현재의 벽을 부순 수보다 클 경우 방문을 하여 그 값을 더 작은 현재의 값으로 대체해주어 탐색을 진행하는 것이었다. 그리고 그 다음이 벽이라면 cnt+1을 벽이 아니라면 cnt 그대로의 값을 다음 좌표와 함께 큐에 push를 해주었다. 이렇게 모든 탐색이 끝나 즉, 큐가 비어지게 되면 visited[n-1][m-1]에는 (n,m)까지 가는데 최소로 벽을 부순 수가 저장이 될 것이다.

코드

# 1261번 알고스팟
from collections import deque
import sys

# main
m, n = map(int, input().split())

board = []
for _ in range(n):
    board.append(sys.stdin.readline())

# bfs
q = deque()
q.append([0,0,0])

# 방문여부
visited = [[float('inf') for _ in range(m)] for _ in range(n)]
visited[0][0] = 0

# 상하좌우
dy = [-1,0,1,0]
dx = [0,-1,0,1]

while q:
    y, x, cnt = q.popleft()

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0 <= ny < n and 0 <= nx < m:
            if visited[ny][nx] > cnt:
                visited[ny][nx] = cnt
                if board[ny][nx] == '1':
                    q.append([ny,nx,cnt+1])    
                else:                    
                    q.append([ny,nx,cnt])

print(visited[n-1][m-1])