오일러 프로젝트 83

이번 문제 역시 80 x 80 행렬에서 움직인 경로의 최소합을 구하는 문제로, 81, 82번에서 한층 더 업그레이드 된 문제라고 한다. 개인적으로는 82번이 좀 더 어려웠다고 생각하는데, 이 83번은 그냥 보통의 다익스트라 알고리듬의 적용 문제이다.

문제

아래와 같은 5×5 행렬이 있습니다. 좌측 상단에서 출발해서 상하좌우로 움직이면서 우측 하단까지 가는 경로의 합을 구해 보면, 빨갛게 표시된 경로가 2297로서 가장 작습니다.

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

접근

시작점과 끝점이 정해져있고, 각 칸의 값은 해당 칸을 지나가기 위한 비용이라고 할 때, 결국 최소비용루트를 구하는 다익스트라다 알고리듬을 적용하면 된다. 보통의 다익스트라다 알고리듬 구현은 그래프 클래스를 만들어서 사용하는데, 여기서는 간단히 1차원 리스트만 사용하는 것으로 구현해보겠다.

이웃찾기

격자 내에서 이웃한 셀의 위치를 찾는 함수를 먼저 작성해보자. 격자의 크기는 width, height 값으로 주어진다고 하고 i 번째 위치에서 상하좌우의 인덱스를 구한다. 이 때, i 값이 격자의 네 모서리 상에 있는지를 검사하여 격자 바깥으로는 나갈 수 없음을 체크해야 한다.

def getNeighbors(i, width, height=None):
  if height is None:
    height = width
  result = []
  if i % width > 0:
    result.append(i-1)
  if (i + 1) % width > 0:
    result.append(i+1)
  if i >= width:
    result.append(i - width)
  if i // width + 1 < height:
    result.append(i + width)

알고리듬 설계

다익스트라다 알고리듬의 구조는 간단하다. 우선 각 노드들은 해당 노드에 방문하기 위한 비용과, 해당 노드까지 도달하기 위한 최소 총 비용 값을 가지고 있게 된다. 방문하지 않은 노드의 최소 총 비용은 무한대로 본다.

그리고 방문한 노드들을 넣어둘 큐를 하나 준비한다. 큐의 초기 상태에는 시작점이 들어있다. 이제 큐에서 하나씩 노드를 꺼내고, 노드의 각 이웃 노드들로의 이동시 총비용을 구한다. 이 때 총비용은 현재노드까지의 총비용 + 이웃노드까지 갔을 때의 비용이 된다. 각 이웃까지의 총비용이 해당 이웃의 기존 총비용보다 작다면, 해당 이웃의 총비용을 업데이트하고 이 이웃을 방문대상 큐에 추가한다.

이 과정을 큐가 빌때까지 반복하면 모든 노드를 1회 이상 방문하고, 모든 노드는 최소총비용으로 방문했다는 것이 보장된다. 이제 원하는 목적지의 노드값을 살펴보기만 하면된다.

만약 전체 경로를 얻고 싶다면, 노드에 직전 노드에 대한 참조를 넣을 수 있게하고, 업데이트 시에 현재노드를 이웃노드의 직전노드로 넣어주면, 목적지로부터 이전노드를 반복적으로 추적하여 경로를 확인할 수 있게 된다.

구현

각 노드를 위한 별도의 클래스를 쓰지 않고, 각각의 노드는 튜플로 취급하겠다. 물론 튜플은 요소값의 업데이트가 되지 않으니,  누적 경로합을 업데이트하는 대신에 해당 노드 자체를 새 튜플로 바꾸는 식으로 처리하겠다.

def search(matrix, width, height=None):
  if height is None:
    height = width
  '''(값, 누적거리, 직전노드)로 정보를 구성한다'''
  temp = [(x, None, None) for x in matrix]
  temp[0] = (temp[0][0], temp[0][0], None)
  queue = [0]

  while queue:
    pos = queue.pop(0)
    c_dist = pos[1]
    for i in getNeighbors(i, width, height):
      v, dist, pred = temp[i]
      n_dist = c_dist + v
      if dist is None or n_dist < dist:
        temp[i] = (v, n_dist, pos)
        queue.append(i)
    return temp[-1][1]

자 이제 문제에 주어진 5×5 행렬에 대해서 최소경로를 구해보자.

sample = [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(search(sample, 5, 5))
# 2297

이제 최종 풀이는 다음과 같다.

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(search(matrix, 80))

main()

더 살펴보기

만약 최소비용 경로상의 각 값들을 확인하고 싶다면 어떻게 해야할까? 위 코드에서는 최소비용 경로를 구성할 때 각 노드의 직전 노드 값을 기록하고 있다. 따라서 목적지로부터 이를 거꾸로 찾아나가면 된다.  위 코드의 search 함수 내에서 while 루프가 끝났을 때 다시 아래 코드를 적용해보자.

c = temp[-1]
result = []
while True:
  result.append(c[0])
  if c[2] is None:
    break
  c = temp[c[2]]
return ' -> '.join(str(x[0]) for x in result[::-1])

샘플데이터에 대해서 실행하면 다음과 같이 경로가 나온다.

131 -> 201 -> 96 -> 342 -> 234 -> 103 -> 18 -> 150 -> 111 -> 422 -> 121 -> 37 -> 331