17484. 진우의 달 여행

17484 문제 보기

접근 방식

으음 틀렸던 문제다 ^.^
처음 내가 접근하고자 하려했던 방법은 이전의 방향을 단계마다 갱신하며,
N개의 행을 하나씩 순회할 때마다 이전 방향과 같지 않은 값 중에 최솟값을 선택하려 했다.
그래서? 한 단계마다 탐욕적으로 답을 선택하는 그리디로 풀이해야겠다고 생각하였다...
하지만 그리디로 풀면 최종 답에 있어 최적해를 구하지 못할 것이 너무 당연했기 때문에
DP로 접근하려고 했었다.
이 문제를 보고 어떻게 풀이해야할지 잘 떠올리는 연습도 제발 해야할 듯 !!!

결론적으로 이 분제는 풀이를 확인한 뒤 DFS로 풀었다.
M개의 열을 순회하면서 dfs 함수에 행, 열, 방향 데이터, 각 칸 별 소요되는 연료, 전체 연료를 넣어 최솟값을 찾아나간다.

low = int(10e9)
for i in range(M):
  low = min(dfs(0, i, 2, low, arr[0][i]), low)

재귀를 통해 이전에 갔던 방향을 제외하고 값을 구해나간다!
요로코롬...

def dfs(col, row, d, low, ans):
  if col == N - 1:
    return min(low, ans)
  
  for i in dx:
    if i != d:
      if 0 <= col < N and 0 <= row + i < M :
        low = dfs(col + 1, row + i, i, low, ans + arr[col+1][row+i])

  return low

최종 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = [list(map(int, input().rstrip().split())) for _ in range(N)]
dx = (-1, 0, 1)

def dfs(col, row, d, low, ans):
  if col == N - 1:
    return min(low, ans)
  
  for i in dx:
    if i != d:
      if 0 <= col < N and 0 <= row + i < M :
        low = dfs(col + 1, row + i, i, low, ans + arr[col+1][row+i])

  return low

low = int(10e9)
for i in range(M):
  low = min(dfs(0, i, 2, low, arr[0][i]), low)

print(low)

배운점

▶️ 문제를 보고 어떻게 풀이해야 하는지 바로 떠올릴 수 있도록 하좟..
▶️ DFS 연습 더 하기!