문제
위와 같은 5 x 5 행렬에서 좌측 상단에서 출발하여 오른쪽이나 아래쪽으로만 움직이면서 우측 하단까지 가는 경로의 합을 구해 보면 아래와 같이 빨갛게 표시된 경로가 2427로서 가장 작습니다.
31KB 짜리 파일 matrix.txt에는 80 x 80 행렬의 정보가 들어있습니다. 위와 같은 방법으로 이 행렬의 좌측 상단에서 출발하여 우측 하단까지 갈 때, 경로합의 최소값은 얼마입니까?
접근
이동하는 방향이 오른쪽과 아래쪽으로 제한적이다. 따라서 행렬 내 임의의 위치에 도달했을 때의 경로합은 1) 왼쪽 위치까지의 경로합 + 해당 위치 값 이거나 2) 위쪽 위치까지의 경로합 + 해당 위치 값이다. 따라서 왼쪽 위부터 시작해서 오른쪽, 아래쪽으로 나아가면서 왼쪽/위쪽의 경로합중에서 작은 것을 취하여 각 항의 최소 경로합을 채워나가는 식의 동적 계획법을 적용할 수 있다.
단, 맨 윗줄일 때에는 오른쪽으로만 이동 가능하며, 또 맨 왼쪽 줄일 때는 아래쪽으로만 이동 가능하다는 규칙만 세우면 된다.
데이터 분석
문제에서 제시하는 URL의 파일은 총 80행이며, 각 행에는 80개의 정수가 컴마로 분리되어 있다. 이를 굳이 이차원 리스트를 쓰지 않고 한 개의 리스트에 쓸어 담아서 사용하면 되겠다. 이때 현재 칸의 인덱스를 i 라고 한다면 왼쪽 칸의 인덱스는 i – 1, 윗 칸의 인덱스는 i – 80이 된다.
풀이
행렬의 왼쪽 위부터 오른쪽으로 순차적으로 스캔하면서 경로의 최소합을 구한다. 이 때 판단해야 하는 경우는 총 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()Julia 풀이
Julia의 경우에는 다차원 배열을 기본적으로 지원해주고 있어서 동일한 동적 계획법으로는 다음과 같이 코드가 만들어진다. Julia의 기본 라이브러리에서 http를 어떻게 사용하는지는 아직 파악하지 못하였으므로, 데이터 파일을 저장해서 사용한다.
별도의 함수를 제작하지 않고 하나의 코드블럭 (실질적으로는 open()함수의 콜백)에서 바로 처리한다. 그외에 Julia의 배열관련 함수 및 다중 변수 for 문의 도움을 받으면 매우 간단한 코드가 나오게 된다.
@time open("/Users/sooop/Downloads/matrix.txt") do f
t = zeros(Int, 80, 80)
m = parse.(Int, hcat(split.(readlines(f), ",")...))
t[1,:] = accumulate(+, m[1,:])
t[:,1] = accumulate(+, m[:,1])
for row=2:80,col=2:80
t[row,col] = min(t[row-1,col], t[row,col-1]) + m[row,col]
end
println(t[end])
end