[백준] 1261번 알고스팟 (by Python)

문제

정말 많은 고민을 하게 하는 문제였다. 많이 볼 수 있는 길 찾기 문제였지만 우선사항이 최단거리가 아니라 최대한 적게 벽을 부수는 방법이었으므로 visited를 활용해 갔던 곳을 못가게 하는 것이 아니라 빙 돌아왔어도 부순 벽의 수가 적다면 수정할 수 있게 하는 것. 이러한 문제의 특징에서 다익스트라를 활용한 포착해낼 수 있었는지의 여부를 묻는 문제였던 것 같다. 나는 아직 미숙해서 거기까지는 눈치채지 못했는데, 앞으로도 더 많은 알고리즘들에 익숙해져 문제에 본질에 어울리는 해결법을 찾는 능력을 길러야겠다.

 

풀이

import sys
import heapq
input = sys.stdin.readline

INF = int(1e9)
m, n = map(int, input().split())
maze = []
smashed = [[INF] * m for _ in range(n)]
for _ in range(n):
    maze.append(list(map(int, input().strip())))

q = []
heapq.heappush(q, (0, 0, 0))
smashed[0][0] = 0
steps = [(1, 0), (0, 1), (-1, 0), (0, -1)]

while q:
    smash, y, x = heapq.heappop(q)
    if smashed[y][x] < smash:
        continue
    for step in steps:
        n_x, n_y = x + step[0], y + step[1]
        if 0 <= n_x < m and 0 <= n_y < n:
            cost = maze[n_y][n_x] + smash
            if cost < smashed[n_y][n_x]:
                smashed[n_y][n_x] = cost
                heapq.heappush(q, (cost, n_y, n_x))

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