[Algorithm] Python3 JUMPGAME 문제 풀이

 

 

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

algospot.com :: JUMPGAME

 

 

JUMPGAME 문제는 N*N의 보드가 주어지고, 왼쪽 제일 위 부분부터 시작하여 오른쪽 제일 아래 부분까지

 

해당 좌표의 숫자 만큼 아래나 오른쪽으로 이동하여 도착할 수 있는지 확인하는 문제이다.

 

(a) 에서는 끝 까지 도착하는 좌표의 예시를 보여주고 있고,

 

(b) 에서는 (a) 부분에서 마지막 경로인 2를 3으로 바꾸어 이동이 불가능한 상황의 예시를 보여주고 있다.

 

풀이

예전에 BOGGLE 문제를 풀 때 가졌던 아이디어를 몇가지 적용시켜봤다.

 

1. 재귀함수에 SOLVED 변수를 선언하여, 재귀를 도는 중에 이미 완료가 되었다면, 더이상 재귀를 실행하지 않음,

 

 - 꽤 괜찮은 아이디어라고 생각한다. 앞으로 푸는 모든 알고리즘 문제에 재귀가 있다면 기본적으로 고려할만 하다.

 

2. 이미 지난 부분은 마킹한다. 

 

 - 이 문제의 복잡도는 최악의 경우 O(N^N )이 된다. 행렬의 전체 경우의 수 가장 최악의 경우 모든 경로를 확인해야한다,

 

그 경우  경우의 수는 해당 식 (_2nC_n) 식과 같다.  

최악의 경우 예시

지난 부분을 마킹하는 메모제이션을 활용하지 않는다면 이 문제는 시간초과가 걸릴 가능성이 높다.

 

여기서 조금 애매한 부분이 있는데, 어떤 좌표 (x,y)에서 이동할 수 있는 경우의 수는 오른쪽 혹은 아래 2가지가 있다.

 

즉 한번만 시도하고, 마킹을 해버리면, 해당 부분을 다시 확인하지 않기 때문에 문제가 생길 수 있다.

 

따라서 오른쪽 혹은 아래로 모두 재귀함수를 보낸 뒤에 메모제이션을 해야한다.

 

이런 문제를 풀다 보면, 역행 분석 (https://en.wikipedia.org/wiki/Retrograde_analysis) 을 하고싶은 생각이 들 수 있다.

 

즉 마지막 끝점에 도달 가능한 경로부터 찾은 뒤, 해당 경로부터 시작점을 되찾아 나가는 방법도 시도해볼 수 있다.

 

하지만, 문제의 케이스가 충분히 주어져 있는 한, 이러한 시도는 크게 의미가 있지 않다.

역행 분석의 최악의 경우 예시

구현

 

 

 

 

 

코드 설명 

 

TEST= int(input())
 
def finder(location):
    global MEMORY
    global GLOBAL_VARIABLE
    # out of boundary
    # 이미 찾았다면 종료
    # 가고자 하는 방향이 이미 있다면
    if GLOBAL_VARIABLE:
        return -1
    elif location[0]>= N or location[1]>= N:
        return -1
    
    elif MEMORY[location[0]][location[1]]==1:
        return -1
 
    elif location[0] ==N-1 and location[1] ==N-1:
        GLOBAL_VARIABLE=1
        return -1
    else:
        jump_size = MAP[location[0]][location[1]]
        MEMORY[location[0]][location[1]]+=1
        finder([location[0]+jump_size,location[1]])
        MEMORY[location[0]][location[1]]+=1
        finder([location[0],location[1]+jump_size])
        
 
for _ in range(TEST):
    N = int(input())
    MAP = []
    MEMORY = [[] for x in range(N)]
    GLOBAL_VARIABLE = 0
    # MAP preparation
    # MEMORY preparation
    # MEMORY [X][Y] = [DOWN,RIGHT]
    for index in range(N):
        temp = input()
        temp = temp.split(" ")
        temp = [int(x) for x in temp]
        MAP.append(temp)
        for _ in range(N):
            MEMORY[index].append(-1)
    finder([0,0])
    if GLOBAL_VARIABLE:
        print("YES")
    else:
        print("NO")

매회 finder 재귀가 돌 때마다, GLOBAL VARIABLE을 참조하여, 이미 끝나지 않았다면 재귀를 지속한다.

 

경로의 바깥으로 가는 경우 해당 재귀를 정지시킨다 (return -1를 활용하여)

 

혹은 이미 갔던 경로일 경우 다시 가지 않는다.

 

눈치 채신 분도 있겠지만, elif의 순서는 가장 가능성이 높은 것부터 체크해주는 것이 좋다.

 

그래야 if문을 덜 돌기 때문,

 

재귀를 돌 때 가장 예상하기 쉬운 것은,

 

재귀를 돌아야 하는 경우 >= 재귀가 완료되었을 경우 >이미 해당 위치를 체크한 경우>=<바운더리 밖에 있을 경우 >위치에 도달한 경우 이다.

 

재귀를 돌아야하는 경우를 if문으로 설정하기 어려워 부득이하게 위치에 도달한 경우를 3번째에 넣었다.

 

위 코드의 결과는 아래와 같고,

바운더리 밖에 있을 경우>=< 이미 해당 위치를 체크한 경우 로 if 문의 순서를 바꾸면 아래와 같게 결과가 나온다.

 

따라서 재귀의 if문은 가능하다면 가장 많이 count가 되는 경우로 설정하는 것이 옳다.