[BOJ 11060] 점프 점프 (Python3)

www.acmicpc.net/problem/11060

11060번: 점프 점프

from collections import deque
 
N=int(input())
graph=list(map(int, input().split()))
visited=[0]*N
 
def bfs():
    queue=deque()
    queue.append(0)
    while queue:
        x=queue.popleft()
        for i in range(1,graph[x]+1):
            nx=x+i
            if 0<=nx<N and visited[nx]==0:
                visited[nx]=visited[x]+1
                queue.append(nx)
if N==1:
    print(0)
else:
    bfs()
    if visited[N-1]==0:
        print(-1)
    else:
        print(visited[N-1])

 

BFS 로 풀었다. 방문하고, 후보 방문지들 큐에 넣고, visited 배열에 후보 방문지들 방문할 때마다 +1을 추가하여 준다.

결과적으로 visited[목적지]에 최소 점프 수가 나올 수 있다.

검색해보니 DP 로도 많이 푼다.

 

개인적으로 BOJ 1697번과 유사해서 쉽게 풀 수 있었다.

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

from collections import deque
 
n,k=map(int, input().split())
MAX=10**5
dist=[0]*(MAX+1)
 
def bfs(n,k):
    queue=deque([n])
    if n==k:
        print(0)
    else:
        while queue:
            x=queue.popleft()
            if x-1==k or x+1==k or x*2==k:
                print(dist[x]+1)
                break
            for i in (x-1, x+1, x*2):
                if i>100000 or i<0 or dist[i]!=0: #이미 방문한것이나 범위를 벗어난것은 탐색하지않음
                    continue
                queue.append(i)     #처음 방문하는 경우에만 붙임
                dist[i]=dist[x]+1
 
bfs(n,k)