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

문제

www.acmicpc.net/problem/1890

1890번: 점프

 

풀이

처음엔 단순한 그래프 문제로 생각했는데, 잘 풀리지 않았다. 

곰곰히 생각해보니 이전에 프로그래머스에서 풀었던 등굣길 문제와 유사했다.

 

좌표 (0, 0)부터 (n-1, n-1)까지 순회하며 현재 좌표(x, y)에서 오른쪽과 아래쪽으로 갈 수 있는지 검사하고, 만약 갈 수 있다면 dp[nx][ny]에 dp[x][y]를 더해준다.

 

이때 dp[y][x] == 0이면 건너뛰는 방식으로 최적화를 해줄 수 있다. 또한 도착 지점(n-1, n-1)에선 g[n-1][n-1] = 0이기 때문에 오른쪽과 아래쪽으로 이동할 수 없다. 따라서 도착 지점은 건너뛰어야 한다.

 

코드

import sys

n = int(sys.stdin.readline().strip())
dp = [[0 for _ in range(n)] for _ in range(n)]
g = []
cnt = 0

for _ in range(n):
    raw = [int(x) for x in sys.stdin.readline().split()]
    g.append(raw)

dp[0][0] = 1

for y in range(n):
    for x in range(n):
        d = g[y][x]
        dx = [0, d]
        dy = [d, 0]

        if not dp[y][x] or (y == n-1 and x == n-1): # 최적화 + 도착 지점 중복계산 방지
            continue

        for i in range(2):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                dp[ny][nx] += dp[y][x]            

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