2 차원 배열에서 두 좌표 사이의 최단 경로를 찾는 방법은 무엇입니까?

2D 배열의 한 지점 (배열의 위치를 ​​나타내는 x 및 y 값이있는 좌표)에서 다른 지점으로 이동하는 가장 짧은 방법을 찾으려고합니다.

초기 좌표에서 최종 좌표까지 이동해야하는 좌표 배열을 출력하고 싶습니다.

이와 같은 배열의 한 예는 다음과 같습니다.

arr = [
          [15, 7, 3],
          [1, 2, 6],
          [7, 4, 67]
      ]

이 경우에서 시작 arr[0][0]하고 끝날 것이라고 말할 수 있습니다 arr[2][2]. 따라서 좌표는 (0, 0)및 (2, 2)입니다.

예상되는 출력은 다음과 같습니다. [(0, 2), (1, 2), (2, 2), (2, 1)]또는 길이가 같은 것입니다.

내가 시도한 것

아래에서 반 성공적인 기능을 만들 수 있었지만 큰 경우에는 매우 비효율적이고 시간이 많이 걸립니다.

import math

arr = [
          [0, 1, 2],
          [3, 4, 5],
          [6, 7, 8]
      ]

coor1 = (0, 0) # seen as 2 in the arr array
coor2 = (2, 2) # seen as 7 in the arr array

def pythagoras(a, b):

    # find pythagorean distances between the two
    distance_y = max(a[0], b[0]) - min(a[0], b[0])
    distance_x = max(a[1], b[1]) - min(a[1], b[1])

    # calculate pythagorean distance to 3 d.p.
    pythag_distance = round(math.sqrt(distance_x**2 + distance_y**2), 3)

    return pythag_distance


def find_shortest_path(arr, position, target):
    ''' finds shortest path between two coordinates, can't go diagonally '''
    coordinates_for_distances = []
    distances = []

    for i in range(len(arr)):
        for r in range(len(arr)):
            coordinates_for_distances.append((i, r))
            distances.append(pythagoras((i, r), target))

    route = []

    while position != target:
        acceptable_y_range = [position[1] + 1, position[1] - 1]
        acceptable_x_range = [position[0] + 1, position[0] - 1]

        possibilities = []
        distance_possibilities = []

        for i in range(len(coordinates_for_distances)):
            if coordinates_for_distances[i][0] == position[0] and coordinates_for_distances[i][1] in acceptable_y_range:
                possibilities.append(coordinates_for_distances[i])
                distance_possibilities.append(distances[i])

            elif coordinates_for_distances[i][1] == position[1] and coordinates_for_distances[i][0] in acceptable_x_range:
                possibilities.append(coordinates_for_distances[i])
                distance_possibilities.append(distances[i])

        zipped_lists = zip(distance_possibilities, possibilities)
        minimum = min(zipped_lists)
        position = minimum[1]
        route.append(position)

    return route