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

🐸 문제 정보

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

 

🤖 알고리즘

dfs

 

⏱️ 풀이 시간

22.22m

 

📝 풀이

처음에 그냥 가중치 그래프 보자마자 허겁지겁 bfs로 풀어버렸다.. 15분 쯤 되어서야 뭔가 이상함을 감지하고 dfs로 변경했다.

하지만 dfs도 n과 m의 범위가 커지면 통과하지 못할 것 같다는 생각이 들었는데, 아니나 다를까 문제에 표기된 알고리즘은 DP였다.

아마 Large에서는 DP로 풀어야 통과되지 않을까 싶다.

우선 이 여기에서는 간단하게 방향을 잡아주고 마지막 행에 도착했을 때 가격의 최소값을 res에 갱신하는 방식으로 풀었다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline
INF = sys.maxsize

n, m = list(map(int, input().rstrip().split()))
board = [list(map(int, input().rstrip().split())) for _ in range(n)]
dy = [-1, 0, 1]

res = INF

def dfs(px, py, pd, cur):
    global res
    if px == n - 1:
        res = min(res, cur)
        return
    for i in range(3):
        ny = py + dy[i]
        if (i != pd) and (0 <= ny < m):
            dfs(px + 1, ny, i, cur + board[px + 1][ny])

for i in range(m):
    dfs(0, i, -1, board[0][i])

print(res)