11048번: 이동하기 / silver 2 / DP

https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

시간 초과 (BFS)

'''
11048번: 이동하기 / silver 2 / BFS
'''
import sys
from collections import deque

input = sys.stdin.readline

# 미로 크기 n,m / 미로 리스트 graph 입력 받기
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
# candy 리스트 / 각 위치 마다, 가장 사탕을 많이 받을 수 있는 개수 넣을 예정
candy = [[-1 for _ in range(m)] for _ in range(n)]
candy[0][0] = graph[0][0]

# BFS 
dx = [1, 0, 1]
dy = [0, 1, 1]
que = deque()
que.append((0, 0, candy[0][0]))
while que:
    x, y, now_candy = que.popleft()
    if now_candy < candy[x][y]:
        continue
    for i in range(3):
        nx = dx[i] + x
        ny = dy[i] + y
        if 0 <= nx < n and 0 <= ny < m:
            next_candy = now_candy + graph[nx][ny]
            if next_candy > candy[nx][ny]:
                candy[nx][ny] = next_candy
                que.append((nx, ny, next_candy))

print(candy[-1][-1])

 

정답 (DP)

'''
11048번: 이동하기 / silver 2 / DP
'''
import sys

input = sys.stdin.readline

# 미로 크기 n,m / 미로 리스트 graph 입력 받기
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

# candy DP 리스트 / 각 좌표 마다, 가장 사탕을 많이 받을 수 있는 개수 넣을 예정
candy = [[0 for _ in range(m)] for _ in range(n)]
for x in range(n):
    for y in range(m):
        if x == 0:
            if y == 0:
                candy[x][y] = graph[x][y]
            else:
                candy[x][y] = graph[x][y] + candy[x][y - 1]
        elif 1 <= x <= n - 1:
            if y == 0:
                candy[x][y] = graph[x][y] + candy[x - 1][y]
            else:
                candy[x][y] = max(graph[x][y] + candy[x - 1][y],
                                  graph[x][y] + candy[x - 1][y - 1],
                                  graph[x][y] + candy[x][y - 1])
print(candy[-1][-1])

 

코드 리뷰

 

- 처음 짠 코드는 BFS로 풀었고, 시간 초과 판정을 받았습니다.

- 각 미로 좌표에서의 가장 사탕을 많이 받을 수 있는 개수를 candy 리스트에 넣어 주었습니다.

 

시간 초과 판정을 받을 후, 생각을 해보니

미로 좌표를 하나씩 쭉 살펴보면서 사탕의 개수를 넣을 수 있다는 것을 알게 되었습니다.

for x in range(n):
    for y in range(m):

        candy[x][y] = ???

 

각 좌표에 넣은 사탕의 개수를 참고하기에 DP라고 할 수 있겠습니당!