[ALGOSPOT] 알고스팟 JUMPGAME 외발 뛰기(Python)

www.algospot.com

[ALGOSPOT] 알고스팟 JUMPGAME 외발 뛰기

(Python)

(글쓴날 : 2020.05.26)

 

---

* ALGOSPOT, 알고스팟 JUMPGAME 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 JUMPGAME 외발 뛰기

---

1) 문제

문제 링크 : https://algospot.com/judge/problem/read/JUMPGAME

algospot.com :: JUMPGAME

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

1부터 9사이의 정수가 적혀있는 격자가 주어지고 격자의 왼쪽 최상단부터 적혀진 숫자만큼 오른쪽 혹은 아래쪽으로 이동하여 오른쪽 최하단으로 갈 수 있는지의 여부를 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였으며, Python을 사용했습니다.

일반 완전 탐색으로 접근할 경우 격자의 최대 크기 n이 100이므로 시간 초과가 발생하게 됩니다.

따라서, memoization을 할 2차원 테이블을 만든 뒤, 동적 계획법을 적용하여 탐색 경로의 중복을 제거해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def DFS(i, j):
    if i > n - 1 or j > n - 1:
        return 0
    if i == n - 1 and j == n - 1:
        return 1
    
    if memoization[i][j] != -1:
        return memoization[i][j]
    
    memoization[i][j] = DFS(i + ground[i][j], j) or DFS(i, j + ground[i][j])
 
    return memoization[i][j]
 
 
C = int(input())
 
for _ in range(C):
    n = int(input())
    ground = [list(map(int, input().split())) for _ in range(n)]
    memoization = [[-1] * n for _ in range(n)]
 
    print("YES" if DFS(0, 0) else "NO")

---