[Python 3] BOJ - 2169 "로봇 조종하기"

 # 문제 링크

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

2169번: 로봇 조종하기

 

 # 풀이

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 이 때 상태공간은 현재 (i, j)에 있고 이전 방향이 k일 때 얻을 수 있는 가치의 최대값으로 정의한다. 문제에서 가장 중요한 조건은 한 번 방문한 곳은 재방문하지 않는 경우인데, 갈 수 있는 방향이 오른쪽, 아래, 왼쪽이기 때문에 이전에 오른쪽에서 왔다면 다음에 왼쪽으로 가는 경우는 재방문하는 경우이다. 마찬가지로 이전에 왼쪽에서 왔다면 다음에 오른쪽으로 가는 경우도 재방문하는 경우이므로 이 두 가지 경우를 제외하면 정답을 구할 수 있다. 주의할 점은 각 좌표에서 얻을 수 있는 가치가 음수도 되기 때문의 음의 무한대로 초기화해주어야 하는 점이다.

 

 # 코드

import sys

# 재귀깊이 해제
sys.setrecursionlimit(100000)

# go : 현재 (x, y)에서 이전 방향이 z였을 때 얻을 수 있는 최대값을 리턴하는 함수
def go(x, y, z):
    # Base Case : 오른쪽 아래에 도달한 경우
    if x == n - 1 and y == m - 1:
        return arr[x][y]
        
    # Memoization
    if dp[x][y][z] != -1:
        return dp[x][y][z]
        
    # 음의 무한대로 초기화
    dp[x][y][z] = -9876543210
    
    for i in range(3):
        # nx, ny : 다음 좌표
        nx, ny = x + dx[i], y + dy[i]
        
        # 오른쪽으로 왔다가 왼쪽으로 가는 경우, 왼쪽으로 왔다가 오른쪽으로 가는 경우는 continue
        if z == 1 and i == 2:
            continue
        if z == 2 and i == 1:
            continue
            
        # 범위 확인 및 점화식
        if 0 <= nx < n and 0 <= ny < m:
            dp[x][y][z] = max(dp[x][y][z], go(nx, ny, i) + arr[x][y])
    return dp[x][y][z]

# 입력부
n, m = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# dx, dy : x좌표와 y좌표의 이동배열
dx = [1,0,0]
dy = [0,1,-1]

# dp : 현재 (x, y)에서 이전 방향이 z였을 때 얻을 수 있는 최대값을 저장하는 상태 공간
dp = [[[-1] * 4 for _ in range(m)] for _ in range(n)]

# 정답 출력
print(go(0,0,-1))