[백준] 1261번 알고스팟 / 파이썬 / python / BFS

📌 문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 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)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

---

👩‍💻 code

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
array=[[int(i) for i in input().rstrip()] for _ in range(n)]

visited=[[-1]*m for _ in range(n)]
print(array)
print(visited)

dx=[-1,1,0,0]
dy=[0,0,-1,1]

from collections import deque
queue=deque()
queue.append((0,0))
visited[0][0]=0

while queue:
    x,y=queue.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if visited[nx][ny]==-1: # 아직 방문 x
                if array[nx][ny]==1: # 벽일 때
                    visited[nx][ny]=visited[x][y]+1
                    queue.append((nx,ny)) # 큐 뒤에 추가
                else: # 빈방일때
                    visited[nx][ny]=visited[x][y]
                    queue.appendleft((nx,ny)) # 큐 앞에 추가
print(visited[n-1][m-1])

---

💕 해설

최소거리 문제이므로 BFS 사용!

visited 배열을 처음에 모두 -1로 해둔 상태에서 시작
첫 시작 부분인 vistied[0][0]을 0으로 바꿔주며 queue에 넣어주면서 시작.

벽을 부술 때 마다 해당 좌표 visited[nx][ny]에 직전 좌표인 visited[x][y]+1 를 해준것을 넣어준다.
빈방이라면 직전 좌표 vistied값 그대로 넣어줌

queue에 방문 좌표를 넣을 땐, 벽이었을 경우는 append로 , 빈방일 경우는 appendleft로 넣어준다.
=> 빈방인 경우가 최소비용의 경우이므로, 먼저 탐색을 끝낼수 있도록 하기 위함!!