[백준] 2169 파이썬

문제

---

• 백준 2169 (골드 2)

백준 2169

n X m 지역의 가치가 주어질 때, (1, 1)부터 (n, m)까지 탐색하는데 탐색한 지역의 가치의 합이 최대가 되도록 하는 문제였다.
문제의 조건은 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다는 것과 한번 탐색한 지역은 다시 탐색하지 않는다는 것이였다.

내 코드

---

우선은 가장 먼저 백트래킹이 떠올라서 생각나는 방식으로 바로 구현해 보았다.
백트래킹을 통해서 모든 경우를 계산하면서 (n, m)에 도달하였을 때 그 가중치가 최대라면 ans를 업데이트해 주었다.
n과 m의 최대값이 1000이라서 조금 불안했는데 아니나다를까 바로 시간초과가 발생하였다.

틀린 코드

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m = map(int, input().split())
mars = [list(map(int, input().split())) for _ in range(n)]
dx = [1, 0, -1]
dy = [0, 1, 0]
visited = [[False] * m for _ in range(n)]
ans = -1 * (10 ** 9)

def back(x, y, w):
    global ans
    if x == m - 1 and y == n - 1:
        ans = max(ans, w)
        return

    for k in range(3):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < m and 0 <= ny < n:
            if not visited[ny][nx]:
                visited[ny][nx] = True
                back(nx, ny, w + mars[ny][nx])
                visited[ny][nx] = False

back(0, 0, mars[0][0])
print(ans)

다음으로는 dp가 떠올라서 이를 활용하여서 코드를 작성하였다.
위쪽으로는 이동할 수 없다는 성질을 이용해서 한줄씩 아래로만 이동하면서 최대값을 계산해주었다.
중복 탐색을 방지하기 위해서 왼쪽에서 접근하는 경우와 오른쪽에서 접근하는 경우를 따로 구하여서 그 최대값을 저장하는 방식으로 구현하였다.

정답 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
mars = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * m for _ in range(n)]
dp[0][0] = mars[0][0]

for i in range(1, m):
    dp[0][i] = dp[0][i -1] + mars[0][i]

for i in range(1, n):
    arr = []
    for j in range(m):
        dp[i][j] = dp[i - 1][j] + mars[i][j]
        arr.append(dp[i][j])

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

    for j in range(m - 2, -1, -1):
        arr[j] = max(arr[j], arr[j + 1] + mars[i][j])

    for j in range(m):
        dp[i][j] = max(dp[i][j], arr[j])

print(dp[n - 1][m - 1])

제출한 코드의 시간을 확인해보니 아슬아슬해서 더 나은 풀이법이 존재하나 찾아보았는데 대부분 비슷한 방식으로 구현한 것 같았다.