99클럽 코테 스터디 14일차 TIL + DFS

문제

Baekjoon 17484: 진우의 달 여행 (Small)

• 설명: 이전과 동일한 방법으로 이동하지 못할 때 최소한으로 지구에서 달까지 이동하는 비용을 구하여라

풀이

• n이 충분히 작기 때문에 단순히 모든 경우의 수를 구하며 가장 비용이 적게 발생하는 경로의 비용을 찾았다.
• 그래프 형식처럼 보여 dfs로 구현하였고 이때 이전에 이동한 위치를 인자로 넣어주어 동일하게 이동하지 않게 하였다.
• 단순하게 생각하면 모든 위치에서 3가지 방향으로 나갈 수 있고 n x m이기 때문에 시간복잡도는 $O(3^n \cdot m)$이다.

오늘의 회고

• 다 풀고 알고리즘 분류를 보니 DP가 있었다.
• 이전에 그 위치로 이동한 방향, 해당 위치를 인덱스, 값을 비용의 최소값으로 3차원 배열로 두면 DP로 풀 수 있다.

Code

# Baekjoon17484.py
MOVES = [-1, 0, 1]

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

mat = [list(map(int, input().split())) for _ in range(n)]

def dfs(row, col, prev, curr):
    if row == n - 1:
        return curr

    result = 0x3f3f3f3f

    new_row = row + 1
    for i in range(len(MOVES)):
        new_col = col + MOVES[i]
        if prev != i and (0 <= new_row < n and 0 <= new_col < m):
            result = min(result, dfs(new_row, new_col, i, curr + mat[new_row][new_col]))

    return result

ans = 0x3f3f3f3f
for i in range(m):
    ans = min(ans, dfs(0, i, -1, mat[0][i]))

print(ans)