11048번 - 이동하기

미로가 주어지고 각 미로의 칸에 사탕이 놓여있다고 가정할 때, 리스트 (0,0) 에서 (N,M)까지 가는데 주울 수 있는 사탕의 최댓값을 구하는 문제입니다.

언뜻 보면 BFS류라고 생각할 수 있으나 DP로 해결 가능합니다.

분석

어제 저는 14494번을 통해 이차원 리스트에서 DP로 최단거리를 구하는 방법에 대해 익혔습니다.
이 문제도 그러한 방식으로 잘 생각해보면 풀이가 나옵니다.

위 그림에 적어놨듯이

리스트[i][j]의 최대 사탕 갯수는 i,j의 옆까지 도달하는데 주워온 사탕의 최대 갯수(dp[i][j-1])와 i,j의 위까지 도달하는데 주워온 사탕의 최대 갯수(dp[i-1][j])를 대조해 더 큰값 + 리스트[i][j]의 사탕갯수

를 계산하게 되면 해당 점화식이 도출되게 됩니다.

코딩

N,M = map(int,input().split())
lst = []
for _ in range(N):
    lst.append(list(map(int,input().split())))

먼저 문제에서 주어진 미로를 받아줍시다.

dp = [[0]*M for _ in range(N)]
dp[0][0] = lst[0][0]

dp리스트를 미로 크기와 똑같이 생성하고 dp[0][0]을 점화식을 위해 lst[0][0]과 똑같이 설정해줍니다.

for i in range(N):
    for j in range(M):
        dp[i][j] = max(dp[i][j-1],dp[i-1][j]) + lst[i][j]

이제 분석단계에서 도출한 점화식을 적용하면 됩니다.

if N == 1:
    print(sum(lst[0]))
else:
    print(dp[N-1][M-1])

마지막 출력부분에서 한가지 주의할 점은 N이 1인 경우입니다.
N이 1이면 세로길이가 1이 되어 점화식을 참고하여 도출하면 이상한 값이 도출됩니다.

세로길이가 1이라면 어차피 미로의 전체 합이 사탕의 최대 갯수가 되므로 미로의 합산을 출력하고
아니라면 도착지점의 dp값을 도출하면 됩니다.