백준 17484 진우의 달 여행 (Small) Python

백준 진우의 달 여행 (Small) 17484 Python 풀이

---

문제

문제 설명

진우는 우주 여행을 떠나기 위해 N×M 격자로 표현된 공간을 지나야 합니다.
각 칸에는 그 칸을 지나갈 때 필요한 연료 소모량이 적혀 있습니다.
우주선의 이동 규칙은 다음과 같습니다.

• 아래로만 내려갑니다.
• 왼쪽 아래 대각선 (↙)
• 바로 아래 (↓)
• 오른쪽 아래 대각선 (↘)
• 같은 방향으로 두 번 연속 이동할 수 없습니다.

출발은 첫 번째 행의 어느 칸에서든 할 수 있고, 도착은 마지막 행의 어느 칸이든 가능합니다.
목표는 최소 연료로 마지막 행까지 도달하는 것입니다.

---

테스트케이스

입력 
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 
출력 
29

---

문제 작동 원리

• 3차원 DP(\(dp[i][j][d]\))를 사용합니다.
• i = 행
• j = 열
• d = 마지막으로 이동한 방향 (0=↙, 1=↓, 2=↘)
• dp[i][j][d] = (i,j)에 도착했을 때, 마지막 이동이 d였을 때 필요한 최소 연료
• 점화식:

\(dp[i][j][d] = \min(dp[i-1][prev][k]) + arr[i][j]\) (단, \(k \neq d\))

• prev는 d에 따라 달라집니다.
• d=0 → prev=j+1
• d=1 → prev=j
• d=2 → prev=j-1
• 마지막 행의 dp 값 중 최소값이 정답입니다.

---

아이디어

• 초기화:
• 첫 번째 행은 arr 값 그대로 초기화 (출발점이므로).
• DP 점화식 적용:
• i=1 행부터 N-1 행까지,
• 각 칸 (i,j)에 대해 3방향(d)을 따로 계산합니다.
• 같은 방향을 연속으로 사용하지 않도록 \(k \neq d\) 조건을 적용합니다.
• 정답 도출:
• 마지막 행(N-1)의 모든 칸과 방향 중 최소값을 출력합니다.

---

전체코드

N, M = map(int, input().split())

arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

INF = 10000000
dp = [[[INF for _ in range(3)] for _ in range(M)] for _ in range(N)]

for i in range(M):
    for j in range(3):
        dp[0][i][j] = arr[0][i]

for i in range(1, N):
    for j in range(M):
        
        # d=0 (왼쪽 아래 대각선, ↙)
        prev_j_0 = j + 1
        if prev_j_0 < M:
            dp[i][j][0] = min(dp[i-1][prev_j_0][1], dp[i-1][prev_j_0][2]) + arr[i][j]

        # d=1 (바로 아래, ↓)
        prev_j_1 = j
        dp[i][j][1] = min(dp[i-1][prev_j_1][0], dp[i-1][prev_j_1][2]) + arr[i][j]

        # d=2 (오른쪽 아래 대각선, ↘)
        prev_j_2 = j - 1
        if prev_j_2 >= 0:
            dp[i][j][2] = min(dp[i-1][prev_j_2][0], dp[i-1][prev_j_2][1]) + arr[i][j]

ans = 100000
for i in range(M):
    ans = min(ans, min(dp[N-1][i]))

print(ans)

---

arr (고정)

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

---

i=0 (초기화: 세 레이어 모두 첫 줄 = arr 0행)

d=0

5 8 5 1 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=1

5 8 5 1 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=2

5 8 5 1 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

---

i=1 (둘째 줄까지 반영: 세 레이어 모두 표시)

arr

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

d=0

5 8 5 1 
11 10 9 ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=1

5 8 5 1 
8 13 13 5 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=2

5 8 5 1 
∞ 10 16 9 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

---

i=2 (셋째 줄까지 반영: 세 레이어 모두 표시)

arr

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

d=0

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=1

5 8 5 1 
8 13 13 5 
20 87 74 14 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=2

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

---

i=3 (넷째 줄부터는: 두 레이어 보여주고 → 남은 1개 레이어의 i=3행만 갱신)

(1) arr, d=1·d=2를 보여주고 → d=0 채우기

arr

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

d=1 (i=2까지 반영 상태)

5 8 5 1 
8 13 13 5 
20 87 74 14 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=2 (i=2까지 반영 상태)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=0 갱신(i=3행만)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
[87 75 19 ∞] 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

---

(2) arr, d=0·d=2를 보여주고 → d=1 채우기

arr

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

d=0 (i=3행까지 반영 상태)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
87 75 19 ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=2 (i=2까지 반영 상태)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=1 갱신(i=3행만)

5 8 5 1 
8 13 13 5 
20 87 74 14 
[21 86 75 16] 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

---

(3) arr, d=0·d=1을 보여주고 → d=2 채우기

arr

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

d=0 (i=3행까지 반영 상태)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
87 75 19 ∞ 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=1 (i=3행까지 반영 상태)

5 8 5 1 
8 13 13 5 
20 87 74 14 
21 86 75 16 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=2 갱신(i=3행만)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
[∞ 20 92 72] 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

---

i=4

(1) arr, d=1·d=2를 보여주고 → d=0 채우기

arr

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

d=1 (i=3행까지 반영)

5 8 5 1 
8 13 13 5 
20 87 74 14 
21 86 75 16 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=2 (i=3행까지 반영)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ 20 92 72 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=0 갱신(i=4행만)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
87 75 19 ∞ 
[25 173 17 ∞] 
∞ ∞ ∞ ∞ 

---

(2) arr, d=0·d=2를 보여주고 → d=1 채우기

arr

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

d=0 (i=4행까지 반영)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
87 75 19 ∞ 
25 173 17 ∞ 
∞ ∞ ∞ ∞ 

d=2 (i=3행까지 반영)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ 20 92 72 
∞ ∞ ∞ ∞ 
∞ ∞ ∞ ∞ 

d=1 갱신(i=4행만)

5 8 5 1 
8 13 13 5 
20 87 74 14 
21 86 75 16 
[92 118 20 77] 
∞ ∞ ∞ ∞ 

---

(3) arr, d=0·d=1을 보여주고 → d=2 채우기

arr

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

d=0 (i=4행까지 반영)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
87 75 19 ∞ 
25 173 17 ∞ 
∞ ∞ ∞ ∞ 

d=1 (i=4행까지 반영)

5 8 5 1 
8 13 13 5 
20 87 74 14 
21 86 75 16 
92 118 20 77 
∞ ∞ ∞ ∞ 

d=2 갱신(i=4행만)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ 20 92 72 
[∞ 119 76 24] 
∞ ∞ ∞ ∞ 

---

i=5

(1) arr, d=1·d=2를 보여주고 → d=0 채우기

arr

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

d=1 (i=4행까지 반영)

5 8 5 1 
8 13 13 5 
20 87 74 14 
21 86 75 16 
92 118 20 77 
∞ ∞ ∞ ∞ 

d=2 (i=4행까지 반영)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ 20 92 72 
∞ 119 76 24 
∞ ∞ ∞ ∞ 

d=0 갱신(i=5행만)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
87 75 19 ∞ 
25 173 17 ∞ 
[122 115 91 ∞] 

---

(2) arr, d=0·d=2를 보여주고 → d=1 채우기

arr

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

d=0 (i=5행까지 반영)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
87 75 19 ∞ 
25 173 17 ∞ 
122 115 91 ∞ 

d=2 (i=4행까지 반영)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ 20 92 72 
∞ 119 76 24 
∞ ∞ ∞ ∞ 

d=1 갱신(i=5행만)

5 8 5 1 
8 13 13 5 
20 87 74 14 
21 86 75 16 
92 118 20 77 
[29 214 84 82] 

---

(3) arr, d=0·d=1을 보여주고 → d=2 채우기

arr

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

d=0 (i=5행까지 반영)

5 8 5 1 
11 10 9 ∞ 
19 90 70 ∞ 
87 75 19 ∞ 
25 173 17 ∞ 
122 115 91 ∞ 

d=1 (i=5행까지 반영)

5 8 5 1 
8 13 13 5 
20 87 74 14 
21 86 75 16 
92 118 20 77 
29 214 84 82 

d=2 갱신(i=5행만)

5 8 5 1 
∞ 10 16 9 
∞ 85 75 14 
∞ 20 92 72 
∞ 119 76 24 
[∞ 120 185 75] 

---

(참고) 마지막 행에서 최소 선택 (최종 답 = 29)

• 열0: \(\min(122, 29, \infty) = 29\)
• 열1: \(\min(115, 214, 120) = 115\)
• 열2: \(\min(91, 84, 185) = 84\)
• 열3: \(\min(\infty, 82, 75) = 75\)
• → 전체 최소 = 29입니다.

---

결론

• 3차원 DP 배열을 사용하여 각 칸, 각 방향의 최소 연료를 모두 저장하면서 진행합니다.
• 핵심은 같은 방향으로 연속 이동 금지 조건을 \(k \neq d\)로 처리하는 것.
• 마지막 행의 모든 dp값 중 최솟값을 정답으로 출력하면 문제 해결이 가능합니다.