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

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

1261번: 알고스팟

Problem

• 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
• 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.
• 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

조건

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

SOL

 

시뮬레이션 문제이지만, 이 문제는 deque의 흐름을 특정 조건에 맞게 bfs가 도는 방식을 control (제어)해야하는 문제이다. 이 문제의 문제점(?) 핵심은, 아래와 같이, 굳이 벽을 부수고 갈 필요가 없다면, 먼 거리에 있더라도(최단거리가 아니라도), 돌아서 간다는 점이다. 

위와 같은 입력이 들어온다면 출력이 0이 나와야한다. 

 

그렇다면, 벽이 있는곳보다,벽이 없는곳을 먼저 방문해야한다. 이걸 구현해주기 위해서는, 우선순위 큐를 이용하는 방법도 있고, deque를 이용해서 앞에 넣을지, 뒤에 넣을지 적절히 통제해서 넣는방법이있다.(appendleft의 기능 이용)

 

우선순위 큐는 우리가 append만해주면 자동으로 관리해준다는 장점이 있지만, 삽입/삭제 과정에서 logn의 시간이 발생하므로, O(1)인 deque를 이용해서 풀어보겠다. (사실, 그렇게 큰 차이는 나지 않을것 같지만, logn도 거의 상수시간에 가까운 아주 좋은 time complexcity이다)

 

#알고스팟
import sys
from collections import deque
input = sys.stdin.readline

M,N =map(int,input().split())
board=[list(map(int,input().rstrip())) for _ in range(N)]
visited=[[0 for _ in range(M)] for _ in range(N)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
ans=sys.maxsize
def bfs(y,x):
    global ans
    dq=deque()
    dq.append((y,x))
    visited[y][x] =1
    while dq:
        y,x= dq.popleft()
        if y==N-1 and x==M-1:
            ans=min(ans,visited[y][x])
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not (0<=ny<N and 0<=nx<M):
                continue
            if not visited[ny][nx]:
                # 0인 곳을 먼저 방문 해준다.
                if board[ny][nx] == 0:
                    dq.appendleft((ny,nx))
                    visited[ny][nx]=visited[y][x]
                
                elif board[ny][nx] ==1:
                    dq.append((ny,nx))
                    visited[ny][nx] = visited[y][x] +1

bfs(0,0)
print(ans-1)
#print(visited)