[알고리즘] 11060 점프 점프
게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 실버 2 (Silver 2) 이상>입니다.
※ 본 사진과 해당 게시글 내용의 문제 모두 백준 : 온라인 저지[Baekjoon_OnlineJudge]사이트에서 발췌해왔습니다.
❓ 문제
백준 온라인 저지 (Baekjoon Online Judge) :11060 점프 점프
❗ 풀이
My Code
(1) DFS 활용
메모리 : 31300KB
시간 : 120ms
해당 풀이는
while문을 통해서
"""
오른쪽 끝 위치에서 시작 해서
매 위치마다 해당 위치부터 최대한 점프할 수 있을 만큼 점프해보는 방법
"""
을 활용한 것이다.
while문에서 idx가 1씩 계속 감소하는데
왼쪽으로 계속 옮겨가면서 비교하는 방식이고
now
를 넘어가야만 now를 확실하게 올 수 있기 때문에
" now와 가장 멀리있는(최소 이동) now까지 점프가능한 위치를 찾기 "를 위해
now를 넘어가는 마지막 가장 오른쪽의 위치를 tmp로 업데이트하고
이 tmp를 다음 dfs 메서드의 인수로 넣어주는 것이다.
def find(now, idx, move):
if now == 0:
return move
tmp = -1
while idx != 0: # 0이 될 때까지
idx -= 1
if Block[idx] + idx < now:
# now보다 크거나 같다 == 도달할 수 있다.
# 해당 위치(idx) + 점프 가능거리 (Block[idx]) >= now
# 여야지만 가능
continue
tmp = idx
# 작아지기 직전값의 위치 (now와 가장 멀리 떨어져잇는 위치) 저장
if tmp == -1:
return -1
move += 1 # 매 실행 : 1회 점프 → 누적시켜주기
return find(tmp, tmp, move)
import sys
input = sys.stdin.readline
N = int(input())
Block = list(map(int, input().split()))
move = 0
print(find(N - 1, N - 1, move))
(2)BFS 활용
메모리 : 32420KB
시간 : 100ms
* 첫값을 시작값으로 bfs에 활용하기 때문에 숫자가 하나밖에 없을 경우엔 while q
내부의 코드에서 범위를 벗어나게 되는 호출이 발생
즉, N==1일 경우는 바로 끝내버려야한다.
이 BFS의 경우엔
가장 왼쪽부터 계산을 시작하는 방법이다.
최초로 도달한 값 == 최소 이동값이라는 점을 활용하기 위해
BFS만 사용하는 것이아닌
DP또한 같이 활용한다.
import sys
input = sys.stdin.readline
N = int(input())
Block = list(map(int, input().split()))
if N == 1:
print(0)
sys.exit()
from collections import deque
counting = [0]*N
q = deque()
q.append([0, Block[0]])
while q :
now , jump = q.popleft()
for i in range(1,jump+1): # for문을 돌려야 넘어가는 경우만 계산되는 실수를 방지할 수있다.
# 최대 점프거리 이내 갈 수 있는 모든 위치 조회
if now + i >= N or counting[now+i] != 0: # 이미 값이 있다는 것은 최솟값이 있다는 것
continue
counting[now+i] = counting[now] + 1
q.append([now+i, Block[now+i]])
if counting[-1] : # 마지막 오른쪽 끝의 값 출력
print(counting[-1])
else : # 0(False) 일 경우
print(-1)
Author And Source
이 문제에 관하여([알고리즘] 11060 점프 점프), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yummygyudon/11060-점프-점프저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)