오일러 프로젝트 82

(참고: 이 문제는 81번 문제의 좀 더 어려운 버전입니다)

아래와 같은 5×5 행렬이 있습니다. 맨 왼쪽 열의 아무곳에서나 출발하여 위/아래/오른쪽으로만 움직이면서 맨 오른쪽 열까지 갈 때, 빨갛게 표시된 경로의 합이 994로 가장 작습니다.

31kB 짜리 파일 matrix.txt에는 80×80 행렬의 정보가 들어있습니다. 위와 같은 방법으로 이 행렬의 맨 왼쪽 열에서 출발하여 오른쪽 열까지 갈 때, 경로 합의 최소값은 얼마입니까?

풀이

81, 82, 83 번 문제는 각각 같은 행렬을 가지고 움직이는 경로의 최소값을 구하는 문제인데, 사이트의 안내와는 달리 개인적으로는 82번 문제가 가장 어려웠다. (83번 문제는 가장 어렵다고는 하지만, 다익스트라다 알고리듬의 변형으로 간단히 풀 수 있는 문제이다.)

두 지점 사이의 경로를 구하는 방식으로는 80개의 출발지와 80개의 도착지를 향하는 총 6400개의 최소합 경로를 구해서 그 중 최소값을 구해야할 것이다. 조금 더 간단하게 한 번에 풀 수 있는 방법이 없을까?

만약, 맨 왼쪽 열의 각 칸 에서 출발해서 최소합을 이루면서 진행해서 오른쪽 열에 도착할 수 있다는 가정을 먼저 해보자. 이 때 N 열의 칸 중에서 임의의 A 행의 칸의 최소 경로는 어떻게 구할 수 있을까?

그전에 행렬의 I열, J행의 칸을 (I, J)라 표현하고 그 칸까지의 최소 경로합을 p(I, J), 그리고 그 칸의 행렬에서의 값을 m(I, J)라 쓴다고 약속하자.

먼저 첫번째 열의 모든 행의 칸을 보자. (1, 1)칸에서 출발할 필요없이 첫 열에서는 바로 해당 행에서 출발할 수 있다. 따라서 제 1 열의 모든 칸의 최소 경로값은 행렬의 해당 행의 값과 같다. (p(1, a) = m(1, a))

이번에는 임의의 한 지점 (A, B)를 보자. 이 지점으로의 최소 경로합은 어떻게 구하면 좋을까?

  1. (A-1, B)에서 오른쪽으로 이동한다 : p(A-1, B) + m(A, B)
  2. (A, B-1)에서 아래로 이동한다 : p(A, B-1) + m(A, B)
  3. (A, B+1)에서 위로 이동한다 : p(A, B+1) + m(A, B)

그런데 같은 열의 다른 값으로부터 최소값을 구하는 것은 문제가 있다. 만약 위에서 아래도 다시 왼쪽에서 오른쪽으로 최소 경로값을 구하다보면 p(A, B+1)까지의 최소 경로값은 아직 구해지지 않은 상황이고, 이 값을 구했을 때 이전 최소 경로합에 영향을 주기 때문에 매번 해당 열의 위쪽 칸들의 값을 재계산해야하기 때문이다.

그래서 A-1 열에서 A열로 이동하는 경우를 항상 오른쪽으로 이동하는 경우로만 제한한다. 즉 위/아래로 이동하는 것은 같은 열에서 먼저 이동한 후에 오른쪽으로 이동하는 것이다. 물론 반대로 오른쪽 이동을 먼저한 후에 움직이는 것이 더 이익이 되는 케이스가 존재하겠지만, 이는 다시 다음 열로 이동하는 과정에서 반복될 동작이라는 것이다.

따라서 p(A, B)를 계산하기 위해서 다음의 방식을 따라보자.

  1. 먼저 B보다 작은 i 에 대해서 (A-1, i)에서 (A, B)로 가는 경로를 계산하면, p(A-1, i) + \sum_{i=0}^{b-1} m(A-1, i) + m(A, B)이 된다.
  2. 반대로 B보다 큰 i 에 대해서는 앞 열에서 위로 이동한 후 오른쪽으로 전진한다. 이 때 경로합은 p(A-1, i) + \sum_{i=b+1}^{80} m(A-1, i) + m(A, B)가 된다.
  3. 끝으로 왼쪽칸에서 오른쪽 칸으로 이동하는 경우에는 p(A-1, B) + m(A, B)로 계산된다.
  4. 이 중에서 가장 작은 값을 취해서 p(A, B)로 사용한다.

즉 특정 칸으로 이동할 때, 왼쪽 열의 모든 칸에서 같은 높이까지 이동한 후에 오른쪽으로 넘어오는 방식으로 계산하여 최소경로를 결정한다. (A, B)까지에 이르는 실제 최소 경로값이 아닐 수 있다. 다만, 이 방식으로 오른쪽으로 나아갔을 때 최우측 열에서의 최소값은 문제에서 요구하는 최소 경로합을 만족할 수 있게 된다.

def minpath(matrix, width):
  size = width * width
  temp = [None] * size
  # 1열의 최소값 채우기
  temp[0::width] = matrix[0::width]
  
  for col in range(1, width):
    for row in range(width):
      # 행렬의 인덱스를 계산
      k = row * width + col
      # 이전열의 경로 리스트
      q = matrix[col-1::width]
      # 기본적으로 왼쪽열의 값을 이전 최소값을 본다.
      cs = temp[k-1]
      
      for i in range(width)
        # 왼쪽열 i 행에서 출발해서 현재 칸까지의 최소 경로를 구한다.
        if i < row:
          s = temp[i*width + col - 1] + sum(q[i+1:row+1])
        elif i == row:
          s = temp[k-1]
        else:
          s = temp[i*width + col - 1] + sum(q[row:i])
        if cs > s or temp[k] is None:
          temp[k] = s + matrix[k]
          cs = s
  # 이렇게해서 구해진 오른쪽 열의 각 행의 값 중에서 최소값을 추출한다.
  return min(temp[(width-1)::width])

자 이제 실제로 문제를 풀어볼 시간이다.

from urllib.request import urlopen

def main():
  url = 'http://euler.synap.co.kr/files/matrix.txt'
  with urlopen(url) as r:
    matrix = sum([[int(x) for x in line.split(',')] for line in\
                   r.read().decode('utf8').splitlines()],  [])
    print(minpath(matrix, 80))

main()