[백준] 17484 진우의 달 여행(small) - python

문제

우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.

[예시]

진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.

1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.

2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.

진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.

최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.

입력

첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다.

다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.

출력

달 여행에 필요한 최소 연료의 값을 출력한다.

문제 해결 아이디어

1. 출발을 가장 연료가 작은 위치에서 한다고 해서 최종 연료 사용량이 작은 것은 아니다.
2. 그래서 출발지 m개에서 시작하여 모든 경우의 수를 확인해야 한다.
3. 이 방식이 dfs 방식과 같기 때문에 dfs 방식으로 이를 풀려고 하였다.

코드

# 진우의 달 여행
# 재귀?

import sys

n, m = map(int, sys.stdin.readline().split(' '))
square = []
for i in range(n):
    square.append(list(map(int, sys.stdin.readline().split(' '))))

direction = [-1, 0, 1]

def dfs(col, row, d, low, answer):
    if col == n-1:
        return min(low, answer)
    for i in direction:
        if i != d:
            if 0 <= col < n and 0 <= row + i < m:
                low = dfs(col+1, row+i, i, low, answer + square[col+1][row+i])
    return low

low = int(sys.maxsize)
for i in range(m):
    low = min(dfs(0, i, 2, low, square[0][i]), low)

print(low)

어려웠던 점

dfs를 많이 구현해본 적이 없어서 return 할 때 어떻게 return 시켜야 할지 고민이 많았다.
일단 가장 작은 것을 고르기 위해서 $low$ 변수를 python에서 나타낼 수 있는 최고 정수를 설정했다.
이후,
우주선이 달에 도착하지 않았으면 -> $low$
우주선이 달에 도착하였으면 -> min(low, answer)
을 리턴하도록 하였다.
왜 min(low, answer)을 해서 리턴하게 하였냐면, 2개 또는 3개의 방향으로 가는 것 중 가장 작은 것을 리턴해야 하기 때문이다.

dfs를 더 수월하게 구현하기 위해 문제를 더 풀어봐야 할 것 같다.