오랜만에 알고리즘 문제를 풀게 되면서 가장 익숙하게 풀었던 DP, BFS를 활용한 문제 중 쉬운문제를 풀어보았다. 깃헙 관리랑 블로그 관리를 2주간 못했다.
다시 원래대로의 루틴을 유지하기 위해서 워밍업 차원에서 정답률 58%인 기본적인 DP문제를 풀어보려고 이 문제를 풀어보게 되었다.
문제 이해 및 적용하기
이 문제는 가장 많이 나오는 유형인 Matrix에서 dp를 저장하면서 가장 마지막의 값이 최대가 될 수 있는 경우의 수를 구하는 것이다.
그 컨셉은 미로로 구성되어 있고, 미로의 칸마다 사탕이 있는데 사람이 (0,0) 에서 입력으로 받아들여지는 (n,m) 까지 가는 동안 사탕을 가장 많이 먹을 수 있는 경우의 수를 구하는 문제이다.
2 가지 방법으로 풀 수 있다.
- for 문으로 dp를 모두 구한 다음에, dp를 출력해주는 것
- Recursion을 통해서 (n,m)을 해주고 recursion 동안 dp가 존재하면 dp를 꺼내주고 dp가 없다면 더 깊이 recursion을 하면서 dp를 구해주는 것
나는 2번째가 익숙해서 2번째 방법으로 풀었다.
# bfs
dx = [-1, -1, 0]
dy = [0, -1, -1]
dp[0][0] = matrix[0][0]
def rec(cy, cx):
maxVal = -1
for i in range(3):
if cy+dy[i] >= 0 and cy+dy[i] < n and cx+dx[i] >= 0 and cx+dx[i] < m:
temLocationVal = dp[cy+dy[i]][cx+dx[i]]
if temLocationVal != -1:
maxVal = max(maxVal,temLocationVal)
else:
maxVal = max(rec(cy+dy[i],cx+dx[i]), maxVal)
dp[cy][cx] = maxVal + matrix[cy][cx]
return dp[cy][cx]
위 코드가 주가 되는 bfs 및 dp 이다.
dx, dy로 문제에서 주어진 3 방향을 순회한 다음에 (지금까지 max 사탕 갯수 + 현재 위치 사탕 갯수) 가 가장 큰 경우의 수를 dp에 저장해주고 return 해준다.
주의할 점
하지만, 생각해보면 (-1,-1)의 경우의 수는 (0,-1), (-1,0)의 경우의 수 보다 클 수가 없으므로 굳이 순회를 해주지 않아도 된다.
본인은 이 경우의 수를 제외하지 않고 문제를 풀이하였으나 정답이 나왔다. 하지만, 효율적인 풀이를 위해서는 이 경우의 수를 제외해주는 것이 좋겠다.
전체코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(40000)
# matrix & dp
n, m = map(int,input().split())
matrix = []
dp = []
for i in range(n):
matrix.append(list(map(int,input().split())))
dp.append([-1 for i in range(m)])
# bfs
dx = [-1, -1, 0]
dy = [0, -1, -1]
dp[0][0] = matrix[0][0]
def rec(cy, cx):
maxVal = -1
for i in range(3):
if cy+dy[i] >= 0 and cy+dy[i] < n and cx+dx[i] >= 0 and cx+dx[i] < m:
temLocationVal = dp[cy+dy[i]][cx+dx[i]]
if temLocationVal != -1:
maxVal = max(maxVal,temLocationVal)
else:
maxVal = max(rec(cy+dy[i],cx+dx[i]), maxVal)
dp[cy][cx] = maxVal + matrix[cy][cx]
return dp[cy][cx]
# excution
print(rec(n-1,m-1))