[BOJ]11048(python)

BOJ - 11048(이동하기) python 풀이

DP를 이용해 풀이

보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서
고민을 했는데

이 문구 덕분에 DP 를 이용해 풀이할 수 있었다
뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다

코드

from collections import defaultdict


def solution():
    N, M = map(int, input().split())
    P = []

    for _ in range(N):
        P.append(list(map(int, input().split())))
    
    count = defaultdict(lambda : defaultdict(int))
    direction = [[0, -1], [-1, 0], [-1, -1]]

    for y in range(N):
        for x in range(M):
            for d in direction:
                by, bx = d[0] + y, d[1] + x
                if count[y][x] < count[by][bx] + P[y][x]:
                    count[y][x] = count[by][bx] + P[y][x]

    print(count[N-1][M-1])

solution()

• 배열을 순회하며 사탕의 갯수를 센다
• 현재 칸의 사탕 갯수 = 현재 칸에서 주어진 사탕 갯수 +
  max(세로 축으로 한칸 전 사탕 갯수, 가로 축으로 한칸 전 사탕 갯수, 가로/세로 한칸 전의 사탕 갯수)
• 마지막 칸의 사탕 갯수를 출력