오일러 프로젝트 81

문제

위와 같은 5 x 5 행렬에서 좌측 상단에서 출발하여 오른쪽이나 아래쪽으로만 움직이면서 우측 하단까지 가는 경로의 합을 구해 보면 아래와 같이 빨갛게 표시된 경로가 2427로서 가장 작습니다.

31KB 짜리 파일 matrix.txt에는 80 x 80 행렬의 정보가 들어있습니다. 위와 같은 방법으로 이 행렬의 좌측 상단에서 출발하여 우측 하단까지 갈 때, 경로합의 최소값은 얼마입니까?

접근

이동하는 방향이 오른쪽과 아래쪽으로 제한적이다. 따라서 행렬 내 임의의 위치에 도달했을 때의 경로합은 1) 왼쪽 위치까지의 경로합 + 해당 위치 값 이거나 2) 위쪽 위치까지의 경로합 + 해당 위치 값이다. 따라서 왼쪽 위부터 시작해서 오른쪽, 아래쪽으로 나아가면서 왼쪽/위쪽의 경로합중에서 작은 것을 취하여 각 항의 최소 경로합을 채워나가는 식의 동적 계획법을 적용할 수 있다.

단, 맨 윗줄일 때에는 오른쪽으로만 이동 가능하며, 또 맨 왼쪽 줄일 때는 아래쪽으로만 이동 가능하다는 규칙만 세우면 된다.

데이터 분석

문제에서 제시하는 URL의 파일은 총 80행이며, 각 행에는 80개의 정수가 컴마로 분리되어 있다. 이를 굳이 이차원 리스트를 쓰지 않고 한 개의 리스트에 쓸어 담아서 사용하면 되겠다. 이때 현재 칸의 인덱스를 i 라고 한다면 왼쪽 칸의 인덱스는 i – 1, 윗 칸의 인덱스는 i – 80이 된다.

풀이

행렬의 왼쪽 위부터 오른쪽으로 순차적으로 스캔하면서 경로의 최소합을 구한다. 이 때 판단해야 하는 경우는 총 4개이다.

1. 시작 항의 경로합은 행렬의 왼쪽 위 값이다.
2. 맨 윗줄은 오른쪽으로만 이동한다.
3. 맨 왼쪽줄은 아래쪽으로만 이동한다.
4. 그외에는 윗칸과 왼쪽칸으로부터 작은 값을 취하여 경로합을 누적한다.

이를 통해 맨 오른쪽 아래의 최종 경로합을 구하는 함수를 작성해보자.

def minPath(matrix: [int], width: int) -> int:
  size = width * width
  temp = [0] * size
  for i in range(size):
    if i is 0:
      temp[0] = matrix[0]
    elif i < width:
      temp[i] = temp[i - 1] + matrix[i]
    elif i % width is 0:
      temp[i] = temp[i - width] + matrix[i]
    else:
      temp[i] = matrix[i] + min(temp[i - 1], temp[i - width])
  return temp[-1]

잘 동작하는지 문제의 행렬을 이용해서 최소 경로합을 계산해보자.

s = [131,673,234,103,18,
     201,96,342,965,150,
     630,803,746,422,111,
     537,699,497,121,956,
     805,732,524,37,331]
print(minPath(s, 5))
# 2427

자 이제 실제 문제를 풀어보자. 네트워크를 통해서 데이터를 받아오더라도 매우 빠르게 풀어낼 수 있다.

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()