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을 출력한다.

 

제한

1 ≤ N,M ≤ 1000

---

처음에는 bfs형식으로 해보려고하였지만 너무 깊이가 깊어질꺼 같았다.

역시나 DP 문제였고 

이를 풀기 위해서 R을 찾고 3방향 탐색 후 갱신 그리고 한 칸씩 옆으로 가면서 탐색하였다.

그리고 빈 공간과 쪽문에서는 현재 값과 이동하기 전을 비교하고 당근은 현재 값과 이동하기 전 + 1을 비교

벽은 이동하지 않고 특히나 쪽문일 때는 현재 당근 수와 지금까지 최대 당근 수를 비교하는 방식으로 하였다.

처음에는 빈공간과 쪽문에서 비교없이 이동하기 전의 값을 갱신하여 틀렸다.

import sys
input = sys.stdin.readline

N, M = map(int,input().split())

# 맵 만들기
maps = [list(input().strip()) for _ in range(N)]

# 토끼 위치 찾기
for i in range(N):
    for j in range(M):
        if maps[i][j] == 'R':
            R = (i,j)

# DP 생성 및 초기화
dp = [[-1] * M for _ in range(N)]
dp[R[0]][R[1]] = 0

# 정답 저장
result = -1

# DP 탐색
# 열을 이동하기 때문에 열 부터 시작
# 토끼 해당 열에서 마지막 전까지
for j in range(R[1],M-1):
    for i in range(N):
        # 해당 위치에서 0이상이면 이동할 수 있는 것을 의미
        if dp[i][j] >= 0:
            # 9시 6시 3시 방향 이동
            for ni in [-1,0,1]:
                nexti = i + ni
                # 범위 안에 들어오는지
                if 0<= nexti < N:
                    # 벽일 때, -1로 유지
                    if maps[nexti][j+1] == '#':
                        continue
                    # 빈 공간일 때, 현재 값과 이동하기 전의 값을 비교
                    elif maps[nexti][j+1] == '.':
                        dp[nexti][j+1] = max(dp[nexti][j+1],dp[i][j])
                    # 당근일 때, 현재 값과 이동하기 전의 값 + 1 을 비교
                    elif maps[nexti][j+1] == 'C':
                        dp[nexti][j+1] = max(dp[nexti][j+1],dp[i][j] + 1)
                    # 쪽문일 때, 현재 값과 이동하기 전의 값을 비교
                    elif maps[nexti][j+1] == 'O':
                        dp[nexti][j+1] = max(dp[nexti][j+1],dp[i][j])
                        # 그리고 지금 결과값과 현재 값을 비교
                        if result < dp[i][j]:
                            result = dp[i][j]

print(result)