백준 1261번: 알고스팟 파이썬

 

1261번: 알고스팟

알아야할 핵심

이 문제도 역시 가중치가 있는 문제이다. 가중치가 모두 같은 일반적인 BFS와 달리 벽이 없는 0으로 가는 길이 벽을 최소로 부술 수 있고, 이때 값이 1일 때보다 우선순위가 높다는 것은 알 수 있을 것이다.

0을 만났을 때, 좀 더 먼저 큐에서 처리될 수 없을까?? 생각했고, 결과적으로 상하좌우로 움직이며, 0을 마주칠 때는 우선순위가 높으므로,  큐에 먼저 append를 하는 appenleft를 사용하는 것으로 방법을 선택했다. 

가중치가 있는 문제임을 알아차리는 것이 오래걸렸다. 그냥 0이 먼저 처리되어야하는데,,, 고민하다 appendleft를 사용하는 방법이 있다는 것을 알게 되었다.

코드

from collections import deque
import sys
input = sys.stdin.readline
m, n = map(int, input().split())
visited = [[-1] * m for _ in range(n)]
room = []
dx = [ -1,1,0,0]
dy = [0,0,-1,1]
for _ in range(n):
    room.append(list(map(int,input().rstrip())))

def bfs(x,y):
    q = deque([(x,y)])
    visited[x][y] = 0
    while q:
        a, b = q.popleft()
        
        for i in range(4):
            nx = dx[i] + a
            ny = dy[i] + b
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if visited[nx][ny] == -1:
                if room[nx][ny] == 1:#벽일때
                    visited[nx][ny] = visited[a][b] + 1
                    q.append((nx, ny))
                else:#벽이 아닐때
                    visited[nx][ny] = visited[a][b]
                    q.appendleft((nx, ny))
           
bfs(0,0)
print(visited[n-1][m-1])