이번 문제는 다익스트라 알고리즘을 활용하여 해결하였다. 다익스트라 알고리즘에서 가중치에 해당하는 리스트에는 검정색 칸을 흰색 칸으로 변경한 횟수가 들어가게 된다. 가중치 리스트의 초기값을 최댓값으로 채운 후, 탐색을 진행하며 더 작은 수가 들어올 경우 갱신해주는 방식으로 해결하였다.

Code

import heapq
n = int(input())
grid = [list(str(input())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def make_maze():
    q = []
    heapq.heappush(q, (0, 0, 0))
    costs = [[1e9 for _ in range(n)] for _ in range(n)]
    costs[0][0] = 0
    while q:
        cost, y, x = heapq.heappop(q)
        if cost > costs[y][x]:
            continue
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                nxt_cost = cost
                if grid[ny][nx] == '0':
                    nxt_cost += 1
                if costs[ny][nx] > nxt_cost:
                    costs[ny][nx] = nxt_cost
                    heapq.heappush(q, (nxt_cost, ny, nx))
    return costs[n-1][n-1]
print(make_maze())