[알고리즘/백준] 11048번 이동하기 Python 파이썬

 

갈수록 DP에 대한 감을 잡아가고 있는 것 같습니다. 이번에도 DP 관련 문제입니다.

 

 

준규가 (1,1) 위치에서 (N, M) 위치까지 갈 때 최대로 얻을 수 있는 사탕의 갯수를 구하는 문제로 지도가 나오길래 BFS 문제인가 흠칫했습니다. DFS든 BFS든 여러 방법으로 풀 수 있는 문제같긴 했습니다. (궁금해서 찾아보니 BFS 로는 가능하고 DFS 경우 메모이제이션을 했다면 전에 값을 구한 적이 있을 때 바로 리턴하는 부분이 있어야 하는데 이 코드에서는 끝에 도달했을 때만 리턴을 할 뿐 메모한 부분을 활용하고 있어 의미가 없다고 하네요. 시간초과 날 경우도 높고)

 

일단 DP 문제로 들어온거라 DP 방식을 사용해서 풀어볼려고 시도해보았습니다. (BFS와 DP 문제 구분법 : BFS는 그래프에서 간선의 가중치가 모두 같을 때의 최단 경로를 구하는 알고리즘 / DP는 부분 문제를 해결하는것으로 더 큰 문제를 해결할 수 있을 때 사용하는 알고리즘 / 위 문제는 정점 사이의 거리는 1이지만, 구하려는 답은 최단 경로가 아니므로 BFS를 적용하기 좋은 문제는 아닙니다.)

 

DP 문제라 생각하니 기본적으로 지도 시작점으로부터 퍼져나가면서 값을 갱신하는 방향 쪽으로 생각하였고 각 지점에 올 수 있는 최대값을 넣어주면 될 거 같았습니다. 물론 각 지점에 도달할 수 있는 방법은 여러가지이기 때문에 늘 기존 값보다 작은지 큰지 비교하여 업데이트 해주었습니다.

 

다음과 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
map_list = []
for i in range(n):
    map_list.append(list(map(int, input().split())))

dx = [1, 0, 1]
dy = [0, 1, 1]

check_list = [ [0]*m for _ in range(n) ] #  dp map
check_list[0][0] = map_list[0][0]

for i in range(n):
    for j in range(m):
        for k in range(3):
            x = i + dx[k]
            y = j + dy[k]
            if 0 <= x < n and 0 <= y < m:
                num = check_list[i][j] + map_list[x][y]
                if check_list[x][y] < num:
                    check_list[x][y] = num

print(check_list[n-1][m-1])

 

다른 분의 풀이를 찾아보니 더 간단히 하는 방법도 있더라고요 비교하는 부분에서

dp[i][j] = map_list[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

으로 요약해서 더 간단하게 처리 가능할 거 같습니다.