[AlgoSpot][Python] 외발 뛰기

🔖 https://www.algospot.com/judge/problem/read/JUMPGAME

---

✏️ 풀이 과정

📝 접근

• 메모이제이션을 적용할 수 있는 간단한 예제이다.

✨ 소스 코드 (일반적인 완전 탐색)

import sys
input = sys.stdin.readline

def solve(y, x):
	# 기저 사례: board의 범위 바깥인 경우
    if y >= n or x >= n: return False
    # 기저 사례: 마지막 칸에 도착한 경우
    if(y == n - 1 and x == n - 1): return True

    jump_size = board[y][x]
    return solve(y + jump_size, x) or solve(y, x + jump_size)

for _ in range(int(input())):
    n = int(input())
    board = []
    for _ in range(n):
        row = list(map(int, input().split()))
        board.append(row)

    print('YES') if solve(0, 0) else print('NO')

✨ 소스 코드 (메모이제이션 적용 후)

import sys
input = sys.stdin.readline

def solve(y, x):
    if y >= n or x >= n: return False
    if(y == n - 1 and x == n - 1): return True
    # 메모이제이션
    if cache[y][x] is not None: return cache[y][x]

    jump_size = board[y][x]
    cache[y][x] = solve(y + jump_size, x) or solve(y, x + jump_size)
    return cache[y][x]

for _ in range(int(input())):
    n = int(input())
    board = []
    for _ in range(n):
        row = list(map(int, input().split()))
        board.append(row)
    cache = [[None] * n for _ in range(n)]

    print('YES') if solve(0, 0) else print('NO')