[BOJ/백준] 1103 게임

import sys

sys.setrecursionlimit(100000)


def dfs(x,y):
    if visited[x][y]:
        return INF
    elif dp[x][y] >0:
        return dp[x][y]
    else:
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]*int(arr[x][y])
            ny = y + dy[i]*int(arr[x][y])
            if 0<=nx<N and 0<=ny<M and arr[nx][ny].isdigit():
                dp[x][y] = max(dp[x][y],dfs(nx,ny) + 1)
                if dp[x][y] == INF:
                    return INF
        visited[x][y] = False
    return dp[x][y]

            





dx = [-1,1,0,0]
dy = [0,0,1,-1]
N,M = map(int,input().split())
INF = float('inf')
arr = [list(input()) for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
dp = [[0 for _ in range(M)] for _ in range(N)]



result = dfs(0,0)

if result == INF:
    print(-1)
else:
    print(result+1)

 

 DP와 DFS를 활용한 문제 였다. 이 와 비슷한 문제를 풀어본 경험이 있었기 때문에 수월하게 풀 수 있었다.

 

여기서 문제에서 동전을 무한번 움직일때 -1을 출력한다는 것은 한번 방문을 했던 곳을 재귀 중에 방문을 하면, 들렸던 

 

장소에서 현재까지 오는 것이기때문에, 무한번 반복할 수 있다는 생각으로 만들어줬다.

 

 

그리고 입력과 똑같은 크기의 DP를 만들어서 해당 값이 초기값인 0이 아닌 다른 값이 있는 것은 해당 위치에서

 

탐색을 끝낸 것이기 때문에 초기값이 아닐때에는 바로 넘겨주는 것을 구현을 했다.

 

 

기본적이 풀이 방식은 다음과 같다.

 

왼쪽 위에서부터 탐색을 하면서, DFS를 처음 들어갈때 방문을 한곳인지 아닌지를 체크한다. 방문을 안한 곳이면,

 

방문을 체크해주고, 현재 위치에서 동서남북으로, 움직임이 가능한 경우를 탐색한다.

 

그리고 가능할때 그 방향으로 DFS를 하면서 한번 움직인 것이기 때문에 + 1을 해준다.

 

이렇게 재귀를 하면서 현재의 DP값과 최대값을 비교해서 저장을 해준다.

 

그리고 이 4방향을 다 둘러본것은 전부 탐색을 한 것이기 때문에 방문을 초기화 해준다.

 

그리고 현재 DP 값을 돌려주면 된다.

 

이렇듯 방문을 체크하는 리스트와 현재 위치에서의 최대값을 저장해주는 DP를 활용해서 풀 수 있는 문제였다.