[99클럽 코테 스터디 14일차 TIL + dp] 백준 17484 진우의 달 여행(small) 파이썬

오늘의 학습 키워드

dp+bfs

공부한 내용 본인의 언어로 정리하기

문제

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

코드

def dfs(x, y, idx, s):
    if x == n - 1:
        ans.append(s)
        return

    for i in range(3):
        if i == idx:
            continue
        else:
            a, b = dir[i]
            nx = x + a
            ny = y + b
            if n > nx >= 0 and m > ny >= 0:
                dfs(nx, ny, i, s + arr[nx][ny])


n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
dir = [(1, -1), (1, 0), (1, 1)]
ans = []

for i in range(m):
    dfs(0, i, -1, arr[0][i])
print(min(ans))

 

dfs에  x, y, 이전 이동 값, 연료 누적 값을 넘겨주며 이전의 이동 값을 지속적으로 확인하고 연료를 누적시킨다. 가질 수 있는 모든 이동 값 중에 가장 작은 수를 출력한다. 

 

오늘의 회고

dp 문제인데 dfs로 푸는게 더 깔끔했던 문제였다. 이전에 방문했던 곳을 고려하면서 가는 방향이 정해져 있음으로 dfs로 깊이탐색을 하면서 답을 찾아나갔다. 별개로 dp 문제는 난이도 상관없이 해당 반복되는 유형을 파악하고 코드로 옮기는 게 힘든 것 같다. 매번 dp문제만 나오면 당황하거나 문제 푸는데 오래 걸리는데 빨리 dp에 익숙해 지도록 문제를 많이 풀어봐야겠다.