[til] 알고리즘 백준 진우의 달 여행 (Small)

🧑‍💻 오늘의 문제: 17484 번 ― 진우의 달 여행 (Small)

지구 ↔ 달 사이의 공간이 N × M 격자(2 ≤ N, M ≤ 6)로 주어지고, 각 칸 값은 그 칸을 통과할 때 소모되는 연료이다.
한 행 아래로 내려갈 때마다 왼쪽‑아래(↙), 아래(↓), 오른쪽‑아래(↘) 중 하나로만 이동할 수 있으며 같은 방향을 두 번 연속 쓸 수 없다.
어느 열에서 출발해도 되고, 어느 열에서 착륙해도 된다. 최소 연료를 구하라. Conquer Mind, Conquer All

---

🚩 알고리즘 분류

• 완전탐색 / 백트래킹

• (또는) DP + 3차원 상태

---

🖥️ 내 풀이 (Python 3 ― 백트래킹)

import sys
sys.setrecursionlimit(10_000)

N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dirs = (-1, 0, 1)        # ↙, ↓, ↘  (열 변위)
INF  = 10**9
best = INF               # 최소 연료

def dfs(r: int, c: int, prev_dir: int, fuel: int):
    """
    r, c     : 현재 위치
    prev_dir : 직전에 사용한 방향(-2 = 시작)
    fuel     : 지금까지 사용한 연료
    """
    global best
    if r == N - 1:       # 달에 도착
        best = min(best, fuel)
        return
    for d in dirs:
        if d == prev_dir:          # 같은 방향 X
            continue
        nc = c + d
        if 0 <= nc < M:
            dfs(r + 1, nc, d, fuel + board[r + 1][nc])

for start_col in range(M):
    dfs(0, start_col, -2, board[0][start_col])

print(best)

⏱ 복잡도

• 경로 수 ≤ M × 3^(N‑1) = 6 × 3⁵ ≒ 1 500 → 완전탐색도 1 초 안에 통과.

---

🔍 다른 풀이: DP (3차원 상태)

INF = 10**9
dp  = [[[INF]*3 for _ in range(M)] for _ in range(N)]

# 출발(첫 행) – “직전에 이동한 방향”이 없으므로 3가지 모두 초기화
for c in range(M):
    for d in range(3):
        dp[0][c][d] = board[0][c]

for r in range(1, N):
    for c in range(M):
        for d in range(3):                       # 이번에 쓸 방향
            pc = c - dirs[d]                     # 이전 열
            if 0 <= pc < M:
                for pd in range(3):              # 직전 방향
                    if pd == d:                  # 같은 방향 금지
                        continue
                    dp[r][c][d] = min(dp[r][c][d],
                                      dp[r-1][pc][pd] + board[r][c])

ans = min(dp[N-1][c][d] for c in range(M) for d in range(3))
print(ans)

• 시간 O(N × M × 3²) ≤ 6×6×9 = 324 → 여유.

• 공간 O(N × M × 3) = 108.

DP는 Small뿐 아니라 Big 버전(17485, N,M ≤ 1 000) 도 같은 로직으로 통과한다.