[백준 2169 🥇] 로봇 조종하기

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

2169번: 로봇 조종하기

문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

출력

첫째 줄에 최대 가치의 합을 출력한다.

 문제 풀이

import sys
from collections import deque

n,m=map(int, sys.stdin.readline().split(' '))
area=[list(map(int, sys.stdin.readline().strip().split(' '))) for _ in range(n)]

# 첫 번째 시작 부분에선 왼쪽, 오른쪽 중 오른쪽으로 밖에 갈 수 없으므로, area를 왼->오 방향으로 변경
for i in range(1,m):
    area[0][i]+=area[0][i-1]
    
dpLeft=[[0]*m for _ in range(n)]
dpRight=[[0]*m for _ in range(n)]
dpRight[0][0]=area[0][0]
dpLeft[0][0]=area[0][0]


for i in range(1, n):
    # dpRight[i][0]은 위에서 내려오는 한 가지 경우만 가능
    dpRight[i][0] = area[i-1][0] + area[i][0]
    # dpLeft[i][-1]은 위에서 내려오는 한 가지 경우만 가능
    dpLeft[i][-1] = area[i-1][-1] + area[i][-1]
    # 오른쪽 방향으로 가는 경우
    for j in range(1,m):
        # 왼쪽에서 오는 방향와 아래에서 내려오는 방향 중 어디가 더 큰지 확인
        dpRight[i][j]=area[i][j]+max(area[i-1][j], dpRight[i][j-1])
    # 왼쪽 방향으로 가는 경우
    for j in range(m-2,-1,-1):
        # 오른쪽에서 오는 방향과 내려오는 방향 중 어디가 더 큰지 확인
        dpLeft[i][j]=area[i][j]+max(area[i-1][j], dpLeft[i][j+1])
    # dpLeft, dpRight 중 어느 값이 더 큰지 비교
    for j in range(m):
        area[i][j]=max(dpLeft[i][j], dpRight[i][j])

print(area[-1][-1])

•  처음엔 단순하게 BFS 풀면 되는 거 아닌가? 싶었는데 BFS를 이용해서 완전탐색을 돌리면 각 경로마다 visited 배열을 선언해주다보니 n,m의 최대 크기가 1000이므로 메모리 초과가 발생한다.
• 다른 방법을 생각해보다가 DP를 떠올리게 되었다.
• DP[i][j]=num은 i행 j열까지 오는데 가질 수 있는 최댓값이 num이라는 것을 의미한다.
• 왼쪽, 오른쪽, 아래로만 움직일 수 있고, 이미 방문한 지점은 다시 방문할 수 없기 때문에 먼저 첫번째 행은 무조건 왼쪽에서 오른쪽으로 향하는 방향만 가능하다.

• 그래서 각 지점의 가치를 입력받은 area 배열의 첫 번째 행을 위와 같은 방식으로 업데이트해준다.
• 다음이 이 문제의 핵심 아이디어다!

• 어떤 지점은 왼쪽에서 오는 방향, 오른쪽에서 오는 방향, 위쪽에서 오는 방향으로 해당 위치에서의 가치의 합을 계산할 수 있다.
• 이 세 가지 방향 중 가장 큰 값으로 area 배열을 갱신해줘야 한다.
• 먼저 dpRight에는 오른쪽 방향으로 진행되므로, dpRight에 저장된 왼쪽에서 오는 값과 area에 저장된 위쪽에서 오는 값을 비교해서 더 큰 값으로 계산해준다.
  • 왼쪽에서 오는 값은 현재 행의 dpRight를 계산 중에 이전에 계산된 값 dpRight[i][j-1]을 사용하고, 위쪽에서 오는 값은 이미 이전 행을 계산하면서 최댓값으로 저장된 값이므로 area[i-1][j] 값을 사용한다.
  • dpRight에서 각 행의 첫 번째는 왼쪽에서 올 수 있는 경로가 없으므로 위쪽에서 오는 값만 가능하다.
• dpLeft도 마찬가지로 왼쪽 방향으로 진행되므로, 오른쪽에서 오는 값과 위쪽에서 오는 값을 비교해서 더 큰 값으로 계산해준다.
  • 오른쪽에서 오는 값은 현재 행의 dpLeft를 계산 중에 이전에 계산된 값 dpLeft[i][j+1]을 사용하고, 위쪽에서 오는 값은 이미 이전 행을 계산하면서 최댓값으로 저장된 값이므로 area[i-1][j] 값을 사용한다.
  • dpLeft에서 각 행의 마지막은 오른쪽에서 올 수 있는 경로가 없으므로 오른쪽에서 오는 값만 가능하다.
• 마지막으로 dpRight와 dpLeft를 비교해서 어느 방향으로 진행하는 쪽이 더 큰 값을 가지는지 비교해서 area에 저장해준다.
• 이와 같이 한 행씩 차례로 계산해나가면서 마지막 area[n-1][m-1]에 저장되는 값이 답이 된다.
• 이 문제의 예제1을 기준으로 계산 과정을 3번째 행까지의 계산 과정을 정리해보면 다음과 같다.

위 그림과 같이 각 위치에서 얻을 수 있는 최대 가치를 한 행씩 area를 갱신해나가면서 얻는다.