[Coding Test][Python][백준] BOJ #17484 진우의 달 여행

 

 

 

 

#17484 진우의 달 여행(Small)

 

문제)

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

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

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

 

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

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

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

입력)

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

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

출력)

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

---

풀이)

※ 풀이 아이디어

N X M 크기의 Matrix에서 최소 연료 비용을 계산하는 문제입니다.(이동 방향이 연속으로 나오면 안됨)
1. DP 사용( DP를 사용해야 겠다는 생각이 드는게 제일 어려웠다. DFS로 풀려다가 실패..)
    같은 방향 연속 금지 조건을 반영하기 위해 3차원 DP Table 사용
2. DP는 점화식을 세우는 것이 가장 중요합니다
    (i-1, j+1)에서 좌하 방향으로 이동 : dp[i][j][0] = min(dp[i-1][j+1][1], dp[i-1][j+1][2]) + matrix[i][j]
    (i-1, j)에서 하 방향으로 이동 : dp[i][j][1] = min(dp[i-1][j][0], dp[i-1][j][2]) + matrix[i][j]
    (i-1, j-1)에서 우하 방향으로 이동 : dp[i][j][2] = min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + matrix[i][j]
3. DP Table의 마지막 행에서 최소값을 도출

# 입력 받기
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

INF = float('inf')

# DP 배열 초기화 (행, 열, 이전 방향)
# dp[i][j][0] : (i-1, j+1)에서 (i, j)로 좌하 방향으로 이동할 때 최소 비용
# dp[i][j][1] : (i-1, j)에서 (i, j)로 하 방향으로 이동할 때 최소 비용
# dp[i][j][2] : (i-1, j-1)에서 (i, j)로 우하 방향으로 이동할 때 최소 비용
dp = [[[INF] * 3 for _ in range(M)] for _ in range(N)]

# 첫 번째 행 초기화
for j in range(M):
    dp[0][j] = [matrix[0][j]] * 3

# DP 갱신
for i in range(1, N):
    for j in range(M):
        # 좌하 방향(↙)으로 이동
        # j+1에서 오기 때문에 j < M - 1이 되어야 한다.
        if j < M - 1:  
            dp[i][j][0] = min(dp[i-1][j+1][1], dp[i-1][j+1][2]) + matrix[i][j]
        
        # 하 방향(↓)으로 이동
        dp[i][j][1] = min(dp[i-1][j][0], dp[i-1][j][2]) + matrix[i][j]

        # 우하 방향(↘)으로 이동
        # j-1에서 오기 때문에 j > 0이 되어야 한다.
        if j > 0:  
            dp[i][j][2] = min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + matrix[i][j]

# 마지막 행에서 최소 연료 소모량 찾기
result = INF
for j in range(M):
    result = min(result, min(dp[N-1][j]))

print(result)

 

주석으로 써 놓았지만 이해를 더 돕기위해 그림을 통해 설명드리겠습니다.

입력 받은 Matrix 값입니다.

위 그림은 DP Table의 초기화 한 상태의 그림입니다.
3차원 배열로 (i, j)에는 각 방향에서 이동한 최소 비용을 나타내는 List를 담고 있습니다.

for문의 첫번째 loop를 수행한 후 DP Table의 값입니다.
현재는 첫번째 행에 모두 동일한 값이 들어가 있어 min 계산이 의미가 있지는 않습니다.

 

for문의 두번째 loop를 수행한 후 DP Table의 값입니다.
i = 2, j = 1일 때의 상황을 화살표를 통해 나타내 보았습니다.
빨간색 선 : dp[2][1][0] = min(dp[1][2][1], dp[1][2][2]) + matrix[2][1] = min(13, 16) + 77 = 90
보라색 선 : dp[2][1][1] = min(dp[1][1][0], dp[1][1][2]) + matrix[2][1] = min(10, 10) + 77 = 87
파란색 선 : dp[2][1][2] = min(dp[1][0][0], dp[1][0][1]) + matrix[2][1] = min(11, 8) + 77 = 85

이러한 과정을 계속 반복하여 마지막 행에 도달하여 최소값을 구하면 해결되게 됩니다.