격자에서 최소 비용 경로를 재귀로 훑기

5x5 격자의 각 칸에 비용이 있고, 왼쪽 아래에서 오른쪽 위로 가는 최소 비용을 구하는 문제다. 움직일 수 있는 방향은 오른쪽, 위, 오른쪽 위 대각선 세 가지다.

1 1 7 2 2
6 8 3 7 4
2 3 9 2 4
5 4 1 6 7
4 2 6 5 9

모든 경로를 만들어 최솟값 고르기

def find(x, y, cur):
    if x == 4 and y == 0:
        cur += map[0][4]
        global li
        li.append(cur)
        return

    if x < 4:
        find(x + 1, y, cur + map[y][x])
    if y > 0:
        find(x, y - 1, cur + map[y][x])
    if x < 4 and y > 0:
        find(x + 1, y - 1, cur + map[y][x])

li = []
find(0, 4, 0)
print(min(li))

세 방향이 세 개의 if 로 그대로 대응된다. 각각 격자 밖으로 나가지 않는지만 확인한다.

비용을 더하는 시점이 조금 특이하다. 다음 칸으로 넘어가면서 지금 칸의 비용을 더한다. 그래서 도착했을 때 목적지 칸의 비용이 아직 안 더해져 있고, 종료 조건 안에서 map[0][4] 를 한 번 더 더한다.

x 와 y 의 순서도 뒤집혀 있다. 인자는 (x, y) 인데 접근은 map[y][x] 다. 격자를 행 우선으로 저장했으니 맞는 접근인데, 함수를 부를 때마다 순서를 뒤집어 생각해야 한다.

방향을 뒤집어 다시

같은 문제를 반대 방향으로도 짰다.

def find(x, y, cur):
    if x == 0 and y == 4:
        cur += map[4][0]
        global li
        li.append(cur)
        return

    if x > 0:
        find(x - 1, y, cur + map[y][x])
    if y < 4:
        find(x, y + 1, cur + map[y][x])
    if x > 0 and y < 4:
        find(x - 1, y + 1, cur + map[y][x])

부등호 방향과 증감만 바뀌었다. 경로의 집합은 같으므로 답도 같아야 한다.

두 셀의 격자 데이터가 한 칸 다르다. 2행 4열이 앞에서는 7이고 뒤에서는 1이다. 그래서 두 답을 나란히 놓고 비교하지는 못했다.

여기서 멈춘 것

이 코드는 경로를 전부 만든다. li 에 모든 경로의 합이 쌓이고 마지막에 min 을 부른다.

같은 칸을 지나는 경로가 수없이 겹치는데, 그 칸까지의 최소 비용은 어느 경로로 왔든 하나다. 칸마다 최솟값을 한 번만 구해두면 다시 훑을 이유가 없다. 방향이 오른쪽과 위쪽으로만 가므로 왼쪽 아래부터 차례로 채워 올라갈 수 있는 형태이기도 하다.

거기까지는 안 갔다. 이 파일에는 완전탐색 두 개만 있다.