<Algorithm>백준_2169 로봇 조종하기

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

처음 문제를 접했을 때, 메모이제이션과 백트래킹 방식을 이용해서 접근했었다.

from collections import deque
n, m = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(n)]
di = (0,0,1)
dj = (1,-1,0)

dp = [[[-1000000001] * 3 for _ in range(m)] for _ in range(n)]

q = deque([(mat[0][0], 0, 0, 0)])
dp[0][0][0] = max(dp[0][0][0], mat[0][0])

c = 0
while q:
    c+=1
    cnt, x, y, pre_d = q.popleft()

    for k in range(3):
        newX, newY = x+di[k], y+dj[k]
        if pre_d^1 == k:
            continue
        if not (0 <= newX<n and 0<= newY<m):
            continue
        if dp[newX][newY][k] < cnt + mat[newX][newY]:
            dp[newX][newY][k] = cnt + mat[newX][newY]

            q.append((cnt + mat[newX][newY], newX, newY, k))

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

code설명

dp(메모이제이션)의 3번째 차원의 개수가 3인 이유는, 임의의 한 점에 도달할 수 있는 가능경로가

위->아래, 왼쪽-> 오른쪽, 오른쪽 -> 왼쪽 이렇게 3가지의 경우가 있기 때문이다.

기본 bfs방식으로 탐색하면서 현재 좌표(x,y)에서 진행할 좌표(newX, newY) 로 갈때의 방향을 기준으로 dp[newX][newY][k]를 갱신할 경우에만 q에 정보를 담으면 결국 dp[-1][-1]에는 3방향으로 부터 들어올 때 가장 큰 값이 저장될 것이다.

하지만 이 코드를 제출하면 시간초과가 뜬다.

n, m = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(n)]

dp = [[-1000000000] * m for _ in range(n)]
left = [[-1000000000] * m for _ in range(n)]
right= [[-1000000000] * m for _ in range(n)]


#1 첫줄작업
dp[0][0] = mat[0][0]
c = 0
for j in range(1, m):
    dp[0][j] = dp[0][j-1] + mat[0][j]
    c += 1

for i in range(1, n):
    # 2 왼->오
    #2.1 left first

    left[i][0] = dp[i-1][0] + mat[i][0]
    for j in range(1, m):
        c += 1
        left[i][j] = max(dp[i-1][j]+mat[i][j], left[i][j-1]+mat[i][j])
    # 3 오 ->왼
    right[i][m-1] = dp[i-1][m-1] + mat[i][m-1]
    for j in range(m-2, -1, -1):
        right[i][j] = max(dp[i-1][j] + mat[i][j], right[i][j+1] + mat[i][j])
        c += 1
    #4 merge
    for j in range(m):
        dp[i][j] = max(right[i][j], left[i][j])
        c += 1
print(dp[n-1][m-1])

code설명

친구에게 물어봤더니 전형적인 dp문제라고 한다. 위에서는 한 좌표를 기준으로 3가지 경로가 있다고 생각해서 bfs적으로 접근했지만 조건을 쪼개보니 다음과 같은 규칙을 찾을 수 있었다.

1. 첫번째 행의 좌표는 왼쪽에서 오른쪽 방향으로 진행하면서 더한값만을 가질 수 있다.(심지어 모두음수이지라도 첫번째행에 속한 dp[i][j]는 무조건 왼쪽부터 시작해서 더해온 총 값이다. )
2. 

위 그림과 같이 이동하며 같은 열의 두 값중 큰 값이 해당 좌표의 가장 큰 총합이 된다.

이런 점화식을 도출해 내는거이 실력이다.

이제시작이다.