[백준]11048(파이썬) - 이동하기

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

11048번: 이동하기

• 나는 알고리즘을 풀 때 거의 입력값이 2차원 배열이면 그래프 아니면 DFS/BFS 일거야 라고 생각을 한 후에 문제를 푸는 안좋은 습관이 있었는데 이 문제를 풀면서 통수를 제대로 맞았다.
• DFS라고 생각하고 문제를 풀었고 테스트 케이스도 많이 넣어봐서 정답임을 확신했지만  n,m이 1000이면 N^2만 되도 100000번의 경우의 수가 생겨버리니까 당연히 시간초과가 발생하는 문제였다.
• 잘보니까 2차원 배열을 이용한 DP문제였다..
• DP임을 인지하고 푸니까 20분정도 밖에 걸리지 않았다. DP로 풀때는 Bottom-up방식으로 메모이제이션기법으로 구현하였다.

#이문제는 dfs문제 라고 생각한 DP 문제
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]

dp =[[0]*(m+1) for _ in range(n+1)]

#dp[0][0] = graph[0][0]

for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+graph[i-1][j-1]
print(dp[n][m])


# #################################################
# DFS 풀이
# def dfs(x,y,candy,visited):
#     global Max
#     if x == n-1 and y == m-1:
#         candy += graph[x][y]
#         if Max<candy:
#             Max = candy
#         return 
#     if 0 <= x < n and 0 <= y < m and visited[x][y] == 0:
#         visited[x][y] = 1
#         dfs(x+1,y,candy+graph[x][y],visited)
#         dfs(x,y+1,candy+graph[x][y],visited)
#         dfs(x+1,y+1,candy+graph[x][y],visited)

# Max = 0
# candy = 0
# visited = [[0]*m for _ in range(n)]
# #dfs(0,0,candy,visited)
# print(Max)