[Python] boj no. 2169 : 로봇 조종하기

Problem

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

Idea

각 지점에 대해서 상좌우 세 방향으로만 이동이 가능하다는 점을 이용한 dp 문제이다.

N이 3이고 M이 5인 지형의 고저차를 나타낸 맵이 다음과 같을 때, dp[i][j]가 좌표 (i, j)까지 도달하기까지 얻을 수 있는 가치의 최대치라고 생각하자.

dp[i][j]의 값은 좌표 (i, j)에 도착할 수 있을 때만 갱신될 수 있고 로봇의 탐색은 (1, 1)부터 시작해서 하좌우 세 방향으로만 움직일 수 있다. 따라서, (1, 2) ~ (1, M)의 dp 값은 (1, 1)에서부터 오른쪽으로 이동하며 고저차를 더한 값이 된다.

2번째 행에 대해서 우선 그 윗 행에서 바로 내려오는 케이스만을 계산하자. 2번째 행의 dp 값은 그 윗 행의 dp 값에서 자기 좌표의 고저차를 더한 값이 된다.

2번째 행에서 위에서 이동하는 케이스는 계산이 되었으므로 양 끝 열을 제외한 좌표들은 양옆에서의 이동만이 가능하다.

2번째 행의 dp 테이블을 분리하여 두 개의 테이블 left와 right를 만든다. left는 오른쪽으로의 이동만이 가능하고 right는 왼쪽으로의 이동만이 가능하다고 생각하자.

left 테이블의 경우 자기 좌표의 dp 값과 자신의 왼쪽 좌표의 dp 값에 자기 좌표의 고저차 값을 더한 값을 비교하여 더 큰 값을 선택한다. 즉, 현재 지점에 위쪽 방향에서 도달하는 방법과 왼쪽 방향에서 도달하는 방법 중 가치가 큰 값을 선택한다. 이를 1번 열부터 M번열까지 반복하면 연속적으로 오른쪽 방향으로 이동할 때의 각 지점의 최대 가치값을 얻을 수 있다.

right 테이블 역시 이동 방향만 반대로 하여 같은 방법으로 최대 가치 값을 구한다.

left 테이블과 right 테이블을 비교하여 더 큰 값을 실제 dp 테이블에 반영한다. 이 과정을 통해 각 지점에 대해 세 방향에서 접근할 때 얻을 수 있는 가장 큰 가치값을 얻을 수 있다.

위의 과정을 N번째 행까지 반복하면 최종적으로 (N, M) 좌표까지 도달하는데의 최대 가치 값을 구할 수 있다.

Code

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
dp = []
for _ in range(N):
    dp.append(list(map(int, input().split())))
    
for i in range(1, M):
    dp[0][i] += dp[0][i-1]
    
for i in range(1, N):
    left = [dp[i][j] + dp[i-1][j] for j in range(M)]
    right = [dp[i][j] + dp[i-1][j] for j in range(M)]
    
    for j in range(1, M):
        left[j] = max(left[j], left[j-1] + dp[i][j])
        
    for j in range(M-2, -1, -1):
        right[j] = max(right[j], right[j+1] + dp[i][j])
        
    for j in range(M):
        dp[i][j] = max(left[j], right[j])
    
print(dp[N-1][M-1])

Comment