[백준/Python] 17484번(DP, 브루트포스)_진우의 달 여행(small)

📌문제 유형

DP, 브루트포스(실버3)

 

📌문제

 

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

 

 

📌나의 문제풀이

- 실패

n,m = map(int,input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

def dfs(graph,x,y,ans,before):  # 이전에 이동한 것 기억하기
    global li
    dx = [1, 1, 1]  # 왼쪽 아래, 아래, 오른쪽 아래
    dy = [-1, 0,1]

    # (n-1번 반복 시 끝남 -> ans값 다 받아서 작은값 출력)
    if x+1 == n :
        li.append(ans)
        return
    
    for i in range(3):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if before != 1:
                dfs(graph,nx,ny,ans + graph[nx][ny],1)
            if before != 2:
                dfs(graph,nx,ny,ans + graph[nx][ny],2)
            if before != 3:
                dfs(graph,nx,ny,ans + graph[nx][ny],3)

result = 100 * n
for i in range(m):
    li = []
    dfs(graph,0,i,0,0)
    if min(li) < result:
        result = min(li)
print(result)

 

📌 다른사람의 문제풀이

 

- DP 이용

[백준][Python] 17484 진우의 달 여행

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
dp = [[[0,0,0] for _ in range(M)]] + [[[float('inf'),float('inf'),float('inf')] for _ in range(M)] for _ in range(N)]

for i in range(1,N+1):
    for j in range(M):
    	# 바로 위, 오른쪽 위에 값만 비교(왼쪽 위의 값 없음)
        if j < M-1:
            dp[i][j][0] = min(dp[i-1][j+1][1],dp[i-1][j+1][2]) + matrix[i-1][j]
        # 바로 위, 왼쪽 위에 값만 비교(오른쪽 위의 값 없음)
        if 0 < j:
            dp[i][j][2] = min(dp[i-1][j-1][1],dp[i-1][j-1][0]) + matrix[i-1][j]
        # 전체 값 비교 가능
        dp[i][j][1] = min(dp[i-1][j][0],dp[i-1][j][2]) + matrix[i-1][j]

min_value = float('inf')
for row in dp[i]:
    for each in row:
        min_value = min(min_value,each)
print(min_value)

 

📌 리뷰 

- 이전의 값 중 최소값을 가져오는 경우 → DP도 생각해보기