점프(백준 1890번)

점프

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

1890번: 점프

 

이 문제를 처음 봤을 때 dfs를 사용해 목적지에 도착하는 경우만 카운트하면 되겠다는 생각으로 풀었다.

그러나 제출하고나니 선명한.. 주황색 '시간초과'를 볼 수 있었다.. 

 

이 문제의 요건은 간단하다. 각 칸에 적혀있는 수 만큼만 점프를 할 수 있으며, 그 방향은 오른쪽과 아래 두 방향으로 고정된다. 이와 같은 규칙으로 가장 오른쪽 아래 칸으로 갈 수 있는 경우의 수를 찾아내면 되는 문제이다.

 

처음 시도했던 dfs의 경우 오른쪽 끝으로 갈 수 있는 모든 경우의 수를 '직접 방문' 하고 카운트하니 당연히 시간초과가 날 수 밖에 없었다..

 

그렇다면 목적지에 딱 한 번 가면서 도착할 수 있는 경우의 수를 찾아야하는데... 대안은 바로 동적 계획법이다!

 

DFS를 사용

# 점프
# 시간초과
import sys

n = int(sys.stdin.readline())

g = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] 
stack = []
stack.append((0,0))
cnt = 0
while stack:
    cx, cy = stack.pop()

    if cx == n-1 and cy == n-1:
        cnt += 1
        continue

    if g[cx][cy] == 0:
        continue

    for i in range(2):
        if i == 0:
            nx = cx + g[cx][cy]
            if 0 <= nx < n:
                stack.append((nx, cy))
        else:
            ny = cy + g[cx][cy]
            if 0 <= ny < n:
                stack.append((cx, ny))
print(cnt)

 

동적 계획법은 메인 문제를 서브 문제로 분리하는것이 중요하다. 이 때 생각해 볼 수 있는 것이, dp 테이블을 만들고 오른쪽 끝 목적지로 바로 가는 경우가 아닌, 특정 좌표로 갈 수 있는 경우의 수를 저장해 두고 이를 사용해서 목적지로 가는 경우의 수를 세보는 것이다. 그리고 테이블은 전부 0으로 초기화 해둔다.

 

다음과 표에 예시가 주어져있다고 하자.

 

시작 위치는 항상 갈 수있는 방법은 1개임으로 dp[0][0] = 1 로 초기화 시켜주자. (0, 0) 위치에서 2칸을 뛰었을 때 갈 수있는 위치는 오른쪽엔 (0, 2) , 아래쪽으론 (2, 0)이다. (인덱스는 0부터 시작한다.) 그럼 dp[0][2]에는 (0, 0)으로 갈 수 있는 경우의수(dp[0][0])를 dp[0][3]에 더해주면 된다. 아래쪽 방향도 마찬가지다.

 

따라서 이 문제의 점화식은 다음처럼 나타 낼 수 있다.

 

jump = g[i][j]

if(i가 맨 아랫칸이 아니고, i+jump가 N보다 작은 경우) d[i+jump][j] += d[i][j]

if(j가 맨 끝칸이 아니고, j+jump가 N보다 작은 경우) d[i][j+jump] += d[i][j]

 

그리고 매 이동시 행렬 밖으로 나가는지 체크해주고, 만약 점프할 수 있는 거리가 0일 경우는 해당 위치에서 목적지로 갈 수있는 방법이 없는 것이기에 뛰어넘으면 된다. 이번 예시는 목적지로 갈 수 있는 경우의 수는 3이 될 것이다.

 

2	3	3 dp[0][0]	1
1	2	1	3
1 dp[0][0]	2 dp[2][0]	3	1 dp[2][1]
3 dp[2][0]	1	1 dp[0][3]	0 dp[3][0] dp[3][2] dp[2][3]

 

DP를 사용한 코드

# 점프
import sys

n = int(sys.stdin.readline())

g = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# '해당 좌표'에 도달 할 수 있는 경우의 수를 저장하는 테이블
# 메인 문제를 서브 문제로 나누는 연습 필요
dp = [[0 for _ in range(n)] for _ in range(n)]
# 시작지의 위치는 항상 갈 수 있는 경우의 수가 1
dp[0][0] = 1
cnt = 0
for i in range(n):
    for j in range(n):
        jump = g[i][j]

        if jump == 0:
            continue

        # 만약 점프해서 해당 위치에 갈 수 있다면
        # 해당 위치의 경우의 수에 출발 위치의 경우의 수를 더해준다.
        if 0 <= i+jump < n:
            dp[i+jump][j] += dp[i][j]
        
        if 0 <= j+jump < n:
            dp[i][j+jump] += dp[i][j]

print(dp[n-1][n-1])

 

DP는 점화식을 찾아내기가 여간 힘든것이 아니다.. 이 역시 문제를 많이 풀어보면 된다는 소문이 있기에.. 열심히 문제를 풀다보면 점화식이 눈에 딱 들어오지 않을까 한다.