문제 링크

1261 - 알고스팟

문제 설명

N*M크기의 미로는 1*1크기의 방으로 이루어져 있다. 각 칸은 빈 방 또는 벽으로 이루어져 있고, 벽은 부수지 않으면 이동할 수 없다.
이동은 상하좌우 인접한 칸으로 가능하다.
현재 (1, 1)에서 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

문제 풀이

BFS + 우선순위 큐로 풀이하면 된다.

[부신 벽의 개수,시작 좌표]를 힙에 넣고, 부신 벽의 개수가 작은 순서대로 차례대로 pop하면서 이동가능한 칸에 대해 다시 append해주면 된다.

import sys
from collections import deque
import heapq

input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def in_bound(x, y):
    if x in range(N) and y in range(M):
        return True
    return False

M, N = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, list(input().strip()))))

queue = []
heapq.heappush(queue, [0,0,0])
visited = [[False for _ in range(M)] for _ in range(N)]
visited[0][0] = 0

while queue:
    count, x, y = heapq.heappop(queue)

    if x == N-1 and y == M-1:
        print(count)
        break

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_bound(nx, ny) and visited[nx][ny] == False:
            if board[nx][ny] == 1:
                heapq.heappush(queue, [count+1, nx,ny])
            else:
                heapq.heappush(queue, [count, nx,ny])
            visited[nx][ny] = True

BFS+우선순위큐 조합의 문제는 처음 풀어보는데 담에 이런 문제 풀때 바로 생각 날라나 ,,