파이썬) 진우의 달 여행 (Small) - BOJ

https://www.acmicpc.net/problem/17484

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

arr = []

for i in range(n):
    arr.append(list(map(int, input().split())))


fuel = 1010101010101010

dy = [0, -1, 1]


def dfs(x, y, p_y, fff, sums_fuel):
    if x == n-1:
        # 달에 도착했으면 현재까지의 연료 합과 여태 계산한 연료합 중 최소값 리턴
        return min(sums_fuel, fff)

    for i in range(3):
        # 방향 설정
        if dy[i] == p_y:
            # 이전에 갔었던 위치라면 건너뜀
            continue
        else:
            nx = x + 1
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                # fff는 dfs함수를 돌며 또는 밑에 for i in range(m)을 돌며 점차 최소값을 갱신해 나간다.
                # 그러므로 최종적으로 리턴 되는 값은 최적의 경로이다.
                # 만일 아래 테케를 그대로 사용한 케이스에서 현재 ff가 100, 그리고 최적의 해가 29라면,
                # 29의 경로에서 달에 닿았을 경우의 최종 합은 29이기 때문에 결국 ff는 29가 된다.

                fff = dfs(nx, ny, dy[i], fff, sums_fuel + arr[nx][ny])

    return fff


for i in range(m):

    fuel = min(dfs(0, i, 100, fuel, arr[0][i]), fuel)

print(fuel)


# 6 4
# 5 8 5 1
# 3 5 8 4
# 9 77 65 5
# 2 1 5 2
# 5 98 1 5
# 4 95 67 58

해당 문제는 dfs + 완전탐색 알고리즘을 사용하여 풀었다.

그런데 dfs를 하도 안풀다보니 dfs함수에서 무엇을 리턴해야할지 고민하느라 시간을 좀 잡아먹었다.

dfs감을 잃었는지 아무래도 dfs문제를 좀 더 풀어봐야할거같다.