[백준] 게임

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

1103번: 게임

DFS + 메모이제이션을 활용하여 해결하였습니다. DFS로 탐색해나가면서 현재 위치부터 움직일 수 있는 최대 횟수를 저장하고 있고 탐색 도중 메모이제이션되어 있는 부분을 만나면 탐색을 진행하지 않고 적혀있는 값을 활용하면 됩니다. 싸이클을 탐색하는 방법은 현재 DFS로 탐색중인 경로를 visited배열로 저장하고 있다가 다음 지점이 visited가 true이면 싸이클이 발생한 경우임을 알 수 있습니다.

 

import sys
sys.setrecursionlimit(10 ** 8)
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

board = [
    list(input().rstrip())
    for _ in range(n)
]


for i in range(n):
    for j in range(m):
        if board[i][j] == 'H':
            board[i][j] = -1
        else:
            board[i][j] = ord(board[i][j]) - ord('0')


dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]

memo = [
    [-1] * m
    for _ in range(n)
]

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

cycleFlag = False

def inRange(y, x):
    return 0 <= x < m and 0 <= y < n

def dfs(y, x):
    global cycleFlag

    if cycleFlag:
        return -1

    mul = board[y][x]
    ret = 0

    for dy, dx in zip(dys, dxs):
        ny = y + mul * dy
        nx = x + mul * dx

        if inRange(ny, nx) and board[ny][nx] != -1:
        	# 현재 탐색중인 경로에서 싸이클이 발생한 경우
            if visited[ny][nx]:
                cycleFlag = True
                return -1

            # 이미 값이 적혀있으면 적혀있는 값 + 1을 리턴한다.
            if memo[ny][nx] >= 0:
                ret = max(ret, memo[ny][nx] + 1)
            # 값이 적혀있지 않으면 리턴 값에 +1을 하여 저장해둔다.
            else:
                visited[ny][nx] = True
                ret = max(dfs(ny, nx) + 1, ret)
                visited[ny][nx] = False

    memo[y][x] = ret

    return ret

visited[0][0] = True
memo[0][0] = dfs(0, 0)

if cycleFlag:
    print(-1)
else:
    print(memo[0][0] + 1)