백준 2169번 : 로봇 조종하기 in Python

2169번: 로봇 조종하기

 

www.acmicpc.net

이 문제는 N*M 크기의 지형에서 로봇을 왼쪽 위에서 오른쪽 아래로 보낼 때 탐사한 지역들의 가치의 합의 최댓값을 구하는 문제이다. 단, 로봇은 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있고, 한 번 탐사한 지역은 다시 탐사할 수 없다.

만약 로봇이 오른쪽, 아래쪽으로만 이동 가능했다면 어떤 경로로 이동해도 한 번 탐사한 지역은 다시 탐사할 수 없어 문제가 되지 않지만, 이 문제는 로봇이 왼쪽으로도 이동 가능하기 때문에 한 지역을 여러 번 방문할 가능성이 생긴다. 그래서 이 문제는 특별히 한 번 탐사한 지역을 다시 탐사할 수 없다는 조건이 붙는다.

로봇의 이동 경로를 예상한다면 위쪽으로는 이동이 불가능하기 때문에 결국 기껏해야 지그재그 형태의 경로로 이동한다고 생각할 수 있다. 그러므로 윗줄부터 각 지역까지 탐사했을 때 가능한 가치의 합의 최댓값을 순서대로 구하면 된다. 맨 윗줄의 경우 각 지역은 오직 오른쪽으로만 이동이 가능하기 때문에 가능한 가치의 합은 한 가지 경우, 즉 왼쪽 위 지역에서 오른쪽으로 계속 이동해 도달하는 방법만으로 얻을 수 있다.

문제는 둘째 줄부터는 세 가지 경우, 즉 윗 지역에서 바로 내려오는 경우, 왼쪽 지역에서 오는 경우, 오른쪽 지역에서 오는 경우를 고려해야 한다. 우선 윗줄의 각 지역에 대해 가치의 합의 최댓값을 구했다고 가정하자. 만약 윗 지역에서 바로 내려오는 경우에는 가치의 합을 구할 때 윗 지역에서 구한 가치의 최댓값에 현재 지역의 가치를 더하면 된다. 왼쪽 지역에서 오는 경우, 왼쪽 지역을 가기 위해서는 그 지역의 왼쪽에서 오거나 위쪽에서 오는 두 가지 경우가 존재한다. 따라서 가치의 합의 최댓값을 구하려면 위 두 가지 경우 중 가치의 합이 더 큰 경우를 선택하면 된다. 마찬가지로 오른쪽 지역에서 오는 경우, 오른쪽 지역을 가기 위해서는 그 지역의 오른쪽에서 오거나 위쪽에서 오는 두 가지 경우 중 가치의 합이 더 큰 경우를 선택하면 된다. 이렇게 하면 한 지역을 두 번 탐사하는 경우를 고려하지 않게 된다. 단, 왼쪽 지역에서 오는 경우를 고려할 때는 같은 줄 내에 있는 지역 중 왼쪽에 있는 지역부터 고려해야 하고, 오른쪽 지역에서 오는 경우를 고려할 때는 같은 줄 내에 있는 지역 중 오른쪽에 있는 지역부터 고려해야 한다. 지그재그 형태의 경로를 생각해보면 그 이유를 쉽게 알 수 있다.

이제 그 줄에 대해 위 작업을 수행한 뒤에는 더 이상 세 경우를 따로 생각할 필요가 없다. 왜냐하면 그 다음 줄을 고려할 때는 현재 줄에서 아래쪽로 내려가는 경우만 생각하기 때문이다. 그러므로 세 경우 중 최대가 되는 값을 뽑아 저장한다.

이를 코드로 구현하면 다음과 같다.

import sys
N, M = map(int, input().split())
mars = []
for _ in range(N):
    mars.append(list(map(int, input().split())))
# 각 지역까지 가는데 탐사한 지역들의 가치의 합의 최댓값을 저장하는 배열
dp = [[-sys.maxsize for j in range(M)] for i in range(N)]
# 각 지역에 도달할 수 있는 세 가지 경우에 대해 탐사한 지역들의 가치의 합의 최댓값을 저장하는 배열
dp2 = [[[-sys.maxsize]*3 for j in range(M)] for i in range(N)]
# 맨 윗줄은 오른쪽으로만 이동 가능하다.
dp[0] = mars[0][:]
for j in range(1, M):
    dp[0][j] += dp[0][j-1]
# 두번째 줄부터는 세 가지 경우를 고려해야 한다.
for i in range(1, N):
    # 윗줄에서 내려오는 경우
    for j in range(M):
        for k in range(3):
            dp2[i][j][k] = dp[i-1][j] + mars[i][j]
    # 왼쪽에서 오는 경우
    for j in range(1, M):
        dp2[i][j][0] = max(dp2[i][j-1][0], dp2[i][j-1][1]) + mars[i][j]
    # 오른쪽에서 오는 경우
    for j in range(M-2, -1, -1):
        dp2[i][j][2] = max(dp2[i][j+1][1], dp2[i][j+1][2]) + mars[i][j]
    # 세 가지 경우 중 가치의 합이 최대가 될 때를 구한다.
    for j in range(M):
        dp[i][j] = max(dp2[i][j])
print(dp[N-1][M-1])