1103번: 게임 (DFS, 메모이제이션)

1103번: 게임

DFS로만 풀려고 하니 시간초과가 떠서 고민하다 DFS에서 탐색을 진행할 때 사이클을 이루는 경우를 제외하고 이전에 탐색한 것과 동일한 탐색을 반복하는 경우가 있다. 예를 들어 아래와 같은 맵이 있다고 하자. 

이때 (0,0) 부터 시작해서 이동가능한 경로를 따라 dfs를 진행한다고하면 아래와 같이 트리를 따라 탐색을 진행한다. 이때 왼쪽에서 오른쪽으로 dfs가 진행되고 있다고 하면 왼쪽에서 dfs를 시행할 때 (1,3)에서 탐색한 것, (3,1)에서 탐색한 것, (1,1)에서 탐색한 것을 다시 탐색을 한다. 탑다운 방식으로 재귀함수를 구현할 때 메모이제이션을 사용했던 것처럼 여기서도 메모이제이션을 이용하면 된다. 

• 트리의 순회를 DFS를 이용해 구현할 수 있고, dfs(x,y) 를 (x,y)에서부터 시작해 동전을 움직일 수 있는 최대 횟수라고 두었다. 그리고 preorder로 트리를 순회하면서 한 노드에서부터 탐색한 값을 dp에 저장해준다. 
• 방문 처리는 2차원 리스트인 visited 를 이용했고 현재 탐색중인 경로로 이동할 때, visited[현재 x][현재 y] 값이 True이면 현재 탐색중인 경로에서 해당 좌표를 방문했었던 것이므로 사이클을 만들 수 있다.   
• 만약 다른 탐색 경로에서 저장한 dp[x][y]가 있으면 이를 dfs(x,y)의 반환값으로 한다. 
• 루트 (x,y)에서 시작해 이동가능한 각 방향의 자식 노드들에 대해서, dp[x][y]는 가능한 이동횟수의 최솟값인 1로 두고, 이후 dfs(자식의 x, 자식의 y) + 1값과 비교하여 더 큰 값으로 dp[x][y]를 설정한다. 

import sys
sys.setrecursionlimit(100000)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append(list(map(str,input())))
visited = [[False for i in range(m)] for j in range(n)]
dp = [[0 for i in range(m)] for j in range(n)]

def dfs(x,y):
    if visited[x][y] == True:
        print(-1)
        exit()
    if dp[x][y] != 0:
        return dp[x][y]
    visited[x][y] = True
    dp[x][y] = 1
    for i in range(4):
        nx = x + dx[i]*int(graph[x][y])
        ny = y + dy[i]*int(graph[x][y])
        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        if graph[nx][ny] == 'H':
            continue
        dp[x][y] = max(dp[x][y],dfs(nx,ny) + 1)
    visited[x][y] = False 
    return dp[x][y]

print(dfs(0,0))