[백준 1103] 게임

1103번: 게임

보드판에서 최대한 머무르는게 목표이므로 최소 비용이 아닌 최대 비용을 구하는 문제 입니다. 그리고 구멍에 빠지거나 보드판 밖으로 나가기 전 까지 머물러야 하기 때문에 최종 목적지가 상황에 따라 다릅니다.

 

최종 목적지가 상황에 따라 다르기 때문에 DFS 돌리되, 스택 보다는 재귀함수를 사용하는 것을 권장합니다. 그래야 (0,0) 위치에서 최장 거리를 구할 수 있으니까요.

 

무한 루프가 돌 수 있기 때문에 visited 배열을 사용해서 방문 여부를 체크합니다. 재귀 함수에 진입했을 때 True로 잡고 재귀함수에서 빠져나오면 해당 위치의 visited를 False로 잡습니다. 4방향의 다른 위치의 방문을 시도했을 때 해당 위치의 visited가 True면 이미 방문한 위치를 또 방문하기 때문에 무한 루프가 되고 이때 -1를 리턴하면 됩니다.

 

속도를 개선하기 위해 해당 위치의 최장 비용을 저장하는 2차원 배열의 DP를 도입합니다. 해당 위치에서 4방향의 최장 거거리들 중 가장 큰 값을 골라 해당 위치의 DP배열에 (최장 거리 + 1)을 저장하면 됩니다. 이렇게 하면 다음 4방향 위치를 확인할 때 DP가 0이상이면 함수를 다시 불러오는 대신 DP의 값만 불러오면 됩니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

n, m = map(int, input()[:-1].split())
di, dj = [0, 0, 1, -1], [1, -1, 0, 0]

g = []
for i in range(n):
    arr = []
    _raw = input()[:-1]
    for j in range(len(_raw)):
        if _raw[j] == 'H':
            arr.append(0)
        else:
            arr.append(int(_raw[j]))
    g.append(arr)

visited = [[False] * m for _ in range(n)]
dp = [[0] * m for _ in range(n)]

def process(i, j):
    v = g[i][j]
    max_cnt = 0
    for k in range(4):
        ni, nj = i + di[k] * v, j + dj[k] * v
        if not ((0 <= ni < n) and (0 <= nj < m)):
            continue
        elif g[ni][nj] == 0:
            continue
        elif visited[ni][nj]:
            return -1
        if dp[ni][nj] > 0:
            max_cnt = max(max_cnt, dp[ni][nj])
        else:
            visited[ni][nj] = True
            w = process(ni, nj)
            visited[ni][nj] = False
            if w == -1:
                return -1
            else:
                max_cnt = max(max_cnt, w)
    dp[i][j] = max_cnt + 1
    return dp[i][j]


visited[0][0] = True
dp[0][0] = 1
ans = process(0, 0)
if ans == -1:
    print(-1)
else:
    print(ans)