[BOJ] 백준 11060 점프점프 - 파이썬

실버 2로 랭크되어있는 백준 11060 점프점프 문제이다. 

 

 

원래 문제풀이는 검색하면 바로 나오기 때문에 필요성을 느끼지 못해서 블로그에 문제풀이 관련 포스팅을 따로 하지 않는데 이 문제의 경우는 좀 아쉬웠다. 메모리 초과로 풀지 못해서 답답한 감이 있어서 포스팅을 하게 되었다. (이 문제는 dp로 풀어내는 방법도 있다고 한다. 처음부터 bfs로 접근했기 때문에 더 아쉬웠다는 생각이 들지만 어차피 어떤 방법으로 접근하든 풀어내는 사람은 문제없이 잘 풀어내기에 단념하고 다른 분들 코드를 읽어보고 있다. )

 

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
# 1이라면 시작과 동시에 종료
if n == 1:
    print(0)
    sys.exit()
    
arr = list(map(int,input().split()))
visited = [0]*n
q = deque([(0,arr[0])]) # 현재 위치, 점프 가능 거리

while q:
    pos,jump = q.popleft()
    for i in range(1,jump+1):
        if pos+i >= n or visited[pos+i]:
            continue
        visited[pos+i] = visited[pos]+1
        q.append((pos+i,arr[pos+i]))
print(visited[-1] if visited[-1] else -1)

 

자 이제 코드를 보자. 

 

일단 n을 입력받는데 n이 1이라면 한칸밖에 없으니 굳이 점프할 필요도 없다. 그렇기 때문에 print 0 을 찍어주고 

곧바로 exit 시키는거다. 

 

이후에 일반적인 문제풀이에서 쓰는 입력을 똑같이 받는다. 그리고 visited 라는 방문 배열도 하나 만들어준다. 

자 그리고 보통 bfs에서 자주 쓰이는 deque 을 쓰기 위해서 덱도 하나 만들어주자. q = deque() 

 

그리고 이제 bfs에서 핵심적으로 쓰이는 부분이 등장한다. while 문 돌면서 덱에 있는 내용 뽑아서 요리조리 조건검사해보고 또 덱에 넣어주고 하는 방식이 진행된다. 

 

덱에서 popleft를 통해 pos, jump 를 빼는데 이후에 바로 for 문을 돈다. 여기서 for문을 돈다는건 점프할 수 있는 모든 구간을 다 확인해보겠다는 말과 같다고 보면 된다. (range를 잘 살펴보라. 1 부터 jump +1 이죠? 점프 가능거리까지 1부터 모두 돌겠다는 소리이다. )

 

자 그렇게 for문을 돌건데 단 조건이 있다! 밖으로 나가면 안되겠죠. 그리고 방문한 곳인데 굳이 또 갈 필요는 없다는거다. 그러니 pos + i 가 n보다 크거나 같거나 혹은 visited[pos + i] 가 true 일때 continue 한다. 즉 생략하고 for 한번 다시 돌겠다는 소리다. 

 

그런 와중에 if 조건에 걸리지 않은 친구들이 아래 부분의 바디를 진행할거고 거기서 내 코드와의 차이점이 나온다. 내 코드가 이 부분을 다르게 풀어서 메모리 초과가 떴다. 

 

visited[pos + i] = visited[pos] + 1  이 코드를 말하는거다. 

즉 이런 코드를 보면 예전에 미로찾기에서 애용했던 방법중의 하나인데 이런 코드가 존재하면 visited 배열의 맨 마지막에 내가 원하는 결과를 넣겠다는 식의 코드가 흔하다. 역시나 마지막에 visited배열에서 -1 즉 마지막 요소를 살피고 있다. 

 

visited[pos + i] = visited[pos] + 1  를 좀 더 살펴보면 visited[pos] 즉 내가 지금 있는 장소에서 다른 곳으로 한번 점프해서 이동할것이기 때문에 +1 이 붙는거다. 한번의 점프라고 보면 된다. 우리는 두번도 세번도 아니고 한번씩 점프하니까 말이다. 그러면 우리가 한번 점프해서 우리가 원하는 pos + i 에 도착했으니 당연히 거기까지 점프한 횟수는 visited[pos] + 1 이 되겠지. 

 

즉 방문 배열이 점프 횟수를 저장하는 용도로 쓰이는거다. 

 

그리고 마지막에서 print 를 해주고 있다. 마지막 요소엔 점프한 횟수가 저절로 저장되어있겠죠. 

 

 메모리 초과로 풀지 못하다니 너무 아쉬운 문제다. 자중합시다.