[ BOJ ] 17130 : 토끼가 정보섬에 올라온 이유 ( GOLD 4 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/17130)

문제

토끼가 정보섬에 올라왔다!

정보섬은 N행 M열의 격자로 나타낼 수 있으며, 어째서인지 여기저기에 당근이 떨어져 있다. 방금 토끼 한 마리가 정보섬 정문으로 들어왔다. 토끼의 왼쪽에선 사나운 늑대가 쫓아오고 있어서, 토끼는 →, ↘, ↗ 방향으로만 이동한다. 토끼는 나가는 길에 최대한 많은 당근을 줍고싶다. 정문은 늑대 때문에 위험하므로 쪽문으로 나가야 하며, 토끼가 당근을 줍기 위해서는 그 당근이 있는 위치를 지나야 한다. 토끼가 어떤 쪽문에 도착했을때 반드시 그 문으로 탈출할 필요는 없으며, 더 움직여서 다른 쪽문으로 탈출해도 된다. 토끼는 얼마나 많은 당근을 주워갈 수 있을까?

토끼의 이동을 명확하게 정의하면 다음과 같다. 격자의 r행 c열 위치를 (r, c)라고 하자. 토끼의 현재위치가 (r, c)일때, 한 번의 이동으로 도착할 수 있는 위치는 (r+1, c+1), (r, c+1), (r-1, c+1)의 3가지다. 벽이나 격자의 밖으로는 이동할 수 없다.

입력

첫 줄에 격자의 크기 N과 M이 주어진다. 그 다음 줄부터 격자의 상태가 N개의 줄에 걸쳐 주어진다. '.'은 빈 공간을, '#'은 벽을, 'R'은 토끼를, 'C'는 당근을, 'O'는 정보섬 쪽문을 나타낸다. 'R'은 반드시 하나만 주어지며, 'O'는 없거나 여러 개일 수 있다.

출력

토끼가 정보섬을 빠져나가면서 얻을 수 있는 당근의 최대 개수를 출력한다. 정보섬에서 빠져나갈 수 없는 경우에는 -1을 출력한다.

풀이 과정

토끼가 움직일 수 있는 방향는  →, ↘, ↗ 이고, 이동할 수 있는 경로에서 얻을 수 있는 당근의 최대 개수를 구해야 하므로 DP 식을 세워 풀이했다.

 

dp[i][j][k] : (i, j) 칸을 지나며 얻을 수 있는 (k[0] 경로 개수 / k[1] 당근 개수)

 

쪽문인 O 를 지나도 계속 이동할 수 있음을 유의하면 쉽게 풀 수 있는 2차원 DP 문제이다.

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
maps = [list(input().rstrip()) for _ in range(n)]
dp = [[[0, 0] for _ in range(m)] for _ in range(n)]
# dp[i][j][k] : (i, j) 를 지나면서 거치는 k[0] 경로 개수 k[1] 최대 당근 개수

col = [-1, 0, 1]
result = -1
for j in range(m):
    for i in range(n):
        if maps[i][j] == 'R': dp[i][j] = [1, 0]
        elif maps[i][j] != '#':
            for d in range(3):
                if j > 0 and 0 <= i + col[d] < n and maps[i][j] != '#' and dp[i + col[d]][j - 1][0] > 0:
                    dp[i][j][0] += dp[i + col[d]][j - 1][0]
                    dp[i][j][1] = max(dp[i][j][1], dp[i + col[d]][j - 1][1])
            
            if maps[i][j] == 'O' and dp[i][j][0] > 0: result = max(result, dp[i][j][1])
            elif maps[i][j] == 'C': dp[i][j][1] += 1

print(result)