문제
풀이
2차원 배열에서 이동하면서 가져올 수 있는 사탕의 최댓값을 구하는 것이 문제이다. 언뜻 보면 bfs나 dfs로 풀어야할 것 같지만 해당 문제의 정석 풀이는 dp로 풀이하는 것이다.
bfs와 dp 문제 구분법
- bfs
- 간선의 가중치가 모두 같을 때 '최단' 경로를 구하는 경우
- dp
- 부분 문제를 해결하는 것으로 더 큰 문제를 해결할 수 있을 때
해당 문제는 정점 사이의 거리는 모두 일정하게 1이지만 최단 경로를 구하는 것이 아니라 최댓값을 구하는 것이므로 dp로 접근하는 것이 더욱 적합하다
dp도 top-down방식과 bottom-up방식 두 가지로 나누어 풀이할 수 있다.
top-down- 큰 문제를 방문한 후 작은 문제를 호출하여 답을 찾는 방식
- 보통 재귀함수로 구현한다 (ex. 피보나치 수열)
bottom-up- 가장 작은 문제부터 답을 구해가며 전체 문제의 답을 찾는 방식
- 보통 반복문으로 구현한다
풀이1. top-down 방식
현재 밟고 있는 미로의 칸까지 어떻게 왔는지에 대해서 생각하며 접근
결론에 도달하기까지의 과정에 대해 역으로 생각하며 접근
dp[i][j] : (1,1)에서 시작하여 (N,M)까지 가는 중에 (i, j) 까지 갔을 때의 가진 최대 사탕의 수
- 왼쪽에서 온 경우 : (i, j-1)에서 온 경우
- 왼쪽 위에서 온 경우 : (i-1, j-1)에서 온 경우
- 위에서 온 경우 : (i-1, j)에서 온 경우
결국 dp[i][j] 는 (i, j)까지 왔을 때까지의 최대 사탕의 수이므로 각 방향에서 오는 dp와 목적지의 사탕의 개수를 더했을 때의 최대값을 다음 dp로 넣는다
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + data[i][j]
전체 코드는 아래와 같다
# Top-down
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
maze = [[0 for _ in range(M + 1)]]
dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
# 인덱스에러 방지를 위해 가장 상단과 가장 좌측에 0 채워 넣음 (의미X)
for i in range(1, N + 1):
maze.append([0] + list(map(int, input().split())))
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]) + maze[i][j]
print(dp[N][M])풀이2. bottom-up 방식
현재 밟고 있는 미로의 칸에서 뻗어갈 수 있는 칸에 대해서 생각하며 접근
결론에 도달하기 위한 과정을 업데이트 해준다고 생각하며 접근
dp[i][j] : (1,1)에서 시작하여 (N,M)까지 가는 중에 (i, j) 까지 갔을 때의 가진 최대 사탕의 수 (top-down 방식과 의미하는 바는 동일)
- 오른쪽으로 (뻗어)가는 경우 : (i, j+1)로 가는 경우
- 대각선으로 (뻗어)가는 경우 : (i+1, j+1)로 가는 경우
- 아래로 (뻗어)가는 경우 : (i+1, j)로 가는 경우
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + data[i+1][j+1]
dp[i+1][j] = max(dp[i+1][j], dp[i][j] + data[i+1][j])
dp[i][j+1] = max(dp[i][j+1], dp[i][j] + data[i][j+1])
전체 코드는 아래와 같다.
# Bottom-Up
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
data = []
dp = [[0 for c in range(M)]for r in range(N)]
for i in range(N):
data.append(list(map(int, input().split())))
dp[0][0] = data[0][0]
for i in range(0, N):
for j in range(0, M):
if i+1<N and j+1 <M:
dp[i+1][j+1] = max(dp[i][j] + data[i+1][j+1], dp[i+1][j+1])
if i+1<N:
dp[i+1][j] = max(dp[i][j] +data[i+1][j], dp[i+1][j])
if j+1<M:
dp[i][j+1] = max(dp[i][j] + data[i][j+1], dp[i][j+1])
print(dp[N-1][M-1])풀이3. dp 최적화
data가 모두 양수라는 조건 때문에 최적화가 가능한데, 칸을 이동할수록 사탕의 개수가 증가하는 구조이므로, 최대한 많은 칸을 들리는 것이 유리하다.
따라서 대각선 방향으로 바로 이동하는 경우(1번 이동)보다 다른 칸을 거쳐 대각선 방향으로 오는 경우(2번이동)가 더 많은 사탕을 가질 수 있다.
풀이1을 최적화한다면,
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + maze[i][j]
풀이2를 최적화한다면,
if i+1<N:
dp[i+1][j] = max(dp[i][j] +data[i+1][j], dp[i+1][j])
if j+1<M:
dp[i][j+1] = max(dp[i][j] + data[i][j+1], dp[i][j+1])
로 코드를 줄여 불필요한 연산을 없앨 수 있다.
풀이4. bfs로 풀기
dp가 정석이지만, bfs, dfs로 풀 수는 있다.
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
mat = []
for i in range(n):
mat.append(list(map(int, input().split())))
score = [[-1 for i in range(m)] for j in range(n)]
score[0][0] = mat[0][0]
dx = [1, 0]
dy = [0, 1]
def bfs(y, x):
q = deque()
q.append([y, x])
while q:
y, x = q.popleft()
for i in range(2):
ny = y + dy[i]
nx = x + dx[i]
if 0 <= nx < m and 0 <= ny < n:
if score[ny][nx] < score[y][x] + mat[ny][nx]:
score[ny][nx] = score[y][x] + mat[ny][nx]
q.append([ny, nx])
bfs(0, 0)
print(score[-1][-1])앞서 언급한 최적화 파트는 bfs에서도 동일하게 적용시킬 수 있으므로 방향을 (우,하)만 두고 풀이할 수 있다. 여기서는 bfs의 visited 역할을 하는 score가 존재한다.
큐에서 꺼낸 현재 위치를 기점으로 아래쪽 또는 오른쪽으로 이동시켰을 때 score[Y][X]가 score[y][x]+mat[Y][X]보다 작다면 해당 값으로 score[Y][X]를 업데이트 시켜준다.
풀이5. dfs로 풀기 (RecursionError)
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)]
# 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)
전형적인 dfs 코드이다. (0, 0)에서 시작해 세 방향으로 좌표를 업데이트 하면서 각각 dfs를 호출한다. 이 때 세 번째 매개변수로 업데이트된 사탕 개수를 넘겨주어야하며, visited 정보 또한 경우의 수 별로 다르게 반영될 수 있게 해야한다. 그렇게 계속 dfs를 진행하다가 y,x 좌표가 n,m에 도달하게 되면 max값을 구하며 return하게 된다.
그치만 상단의 코드는 recursion error를 발생시킨다 🥲
Reference
