BOJ 1890 점프

LONGNEW·2021년 3월 7일
0

BOJ

목록 보기
192/333

https://www.acmicpc.net/problem/1890
시간 1초, 메모리 128MB
input :

  • N (4 ≤ N ≤ 100)
  • 각 칸에 적혀져 있는 수가 N개씩

output :

  • 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력

조건 :

  • 반드시 오른쪽이나 아래쪽으로만 이동해야 한다

BOJ 2253 내리막길 문제와 유사한 문제이다.

특정한 조건인 오른쪽, 아래쪽으로만 이동하는데 이를 생각하지 않아 한 번 틀렸다.

그리고 이미 방문을 한 지점에서도 마지막까지 이동한 경로가 존재할 수 있다. 그래서 모든 지점에서의 경로 값을 합해 줘야 한다.

import sys


def dfs(x, y):
    if x == n - 1 and y == n - 1:
        return 1

    if visit[x][y] == -1:
        visit[x][y] = 0
        mv = data[x][y]

        for dx, dy in [(mv, 0), (0, mv)]:
            nx = x + dx
            ny = y + dy

            if nx >= n or nx < 0 or ny >= n or ny < 0:
                continue
                
            visit[x][y] += dfs(nx, ny)

    return visit[x][y]


n = int(sys.stdin.readline())
data = []
for i in range(n):
    data.append(list(map(int, sys.stdin.readline().split())))

visit = [[-1] * n for i in range(n)]
dfs(0, 0)

print(visit[0][0])

0개의 댓글