[백준] 1890번 점프 (파이썬/Python) - DP

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

1890번: 점프

최근 계속 밤새서 팀플하고 사랑니뽑고 아팠다가 다시 회복하고 백준 달린다 ㅎㅎ ..

n = int(input())
array = []
answer = 0
for _ in range(n):
    array.append(list(map(int, input().split())))

# 오른쪽, 아래
dx = [0, 1]
dy = [1, 0]

visited = [[False] * n for _ in range(n)]
def dfs(x, y):
    global answer
    if x == n-1 and y == n-1:
        answer += 1
        return
    for i in range(2):
        # 반드시 array[x][y] 칸 만큼 이동
        nx = x + dx[i]*array[x][y]
        ny = y + dy[i]*array[x][y]

        if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny)
            visited[nx][ny] = False


visited[0][0] = True # start point
dfs(0, 0)
print(answer)

dfs로 백트래킹하면 시간초과가 난다  그럴줄 알았지만..역시 ㅎ

라고 문제에서 써놓은 이유가 있겠지 ? 2**63-1 을 계산하면 .. 9223372036854775807 라는 숫자가 찍한다 
dfs 재귀호출하면 당연히 시간초과/메모리초과가 날 수 밖에 없는 구조이다 

이를 해결하기 위해 DP로 푸는 방법이 있다. 
생각해보면 간단한 것이 이동방법이 2가지 밖에 없다. 

n = int(input())
array = []

for _ in range(n):
    array.append(list(map(int, input().split())))


# dp 에 array(i,j) 를 지나는 경우의 수(경로) 를 저장한다.
dp = [[0]*n for _ in range(n)]
dp[0][0] = 1

for x in range(n):
    for y in range(n):
        if x == n-1 and y == n-1: # 여기서 멈춰야 구하고 싶은 값 출력 가능 
            print(dp[-1][-1])
            break
        # 오른쪽  (0, 1) 증가
        if y + array[x][y] < n: # 이동 가능 범위인지 확인
            dp[x][y + array[x][y]] += dp[x][y]

        # 아래로 이동
        if x + array[x][y] < n:
            dp[x+array[x][y]][y] += dp[x][y]

1) dp 는 n*n 의 2차원 배열으로 생성해 준다. 앞으로의 연산을 위해 dp[0][0] 을 1로 초기화한다. 

2) 오른쪽으로 이동하는 경우 / 아래쪽으로 이동하는 경우를 확인한다 
문제에서 그래도 친절하게 x 값을 바꾸는 경우, y 값을 바꾸는 경우 2가지로 제한했다는 생각이 든다.. 

먼저 오른쪽으로 이동하는 경우 y 좌표의 값이 증가해야 하고, 범위 내에 있어야 한다. 

if y + array[x][y] < n: # 이동 가능 범위인지 확인

조건을 만족하면, 이동할 좌표에 해당하는 공간을 dp 2차원 리스트에서 접근한다. 
이동경로는 이전 위치인(x,y)에서부터 쭉 한가지 경로가 되는 것이므로 dp[x][y] 에 있던 값을 그대로 가져와서 더해준다. 

dp[x][y + array[x][y]] += dp[x][y]

또한 아래쪽으로 이동하는 경우 x 좌표의 값이 증가해야 하고, 범위 내에 있어야 한다. 오른쪽으로 이동하는 경우와 마찬가지로 연산한다. 

# 아래로 이동
if x + array[x][y] < n:
    dp[x+array[x][y]][y] += dp[x][y]