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])
