이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 가중치에 대한 정의에 고민을 조금 하였고, 결과적으로 0이 아닌 값을 만날 경우에 다음 가중치를 1 증가시키는 방식으로 접근하였다. 최소힙을 사용하여 시간을 줄였고, 가중치에 해당하는 dists는 초기값을 1e9로 하여 최솟값을 찾을 수 있도록 하였다.

Code

import heapq
n, m = map(int, input().split())
y1, x1, y2, x2 = map(int, input().split())
y1, x1, y2, x2 = y1-1, x1-1, y2-1, x2-1
grid = [list(str(input())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def jump():
    hq = []
    heapq.heappush(hq, (0, y1, x1))
    dists = [[1e9 for _ in range(m)] for _ in range(n)]
    dists[y1][x1] = 0
    while hq:
        dist, y, x = heapq.heappop(hq)
        if dist > dists[y][x]:
            continue
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m:
                nxt_dist = dist
                if grid[ny][nx] != '0':
                    nxt_dist += 1
                if dists[ny][nx] > nxt_dist:
                    dists[ny][nx] = nxt_dist
                    heapq.heappush(hq, (nxt_dist, ny, nx))
    return dists[y2][x2]
print(jump())