[BOJ] 1697번 : 숨바꼭질
1. 문제
- 수빈 N(0 ≤ N ≤ 100000)에서 동생 K(0 ≤ K ≤ 100000)까지 이동
- 현재 위치를 X라 할 때,
- 걸으면 1초 후 X - 1 또는 X + 1로 이동
- 순간이동을 하면 1초 후 2 * X로 이동
- 동생까지 이동하는데 가장 빠른 시간
2. 알고리즘
- BFS
- X - 1, X + 1, 2 * X를 자식으로 하는 트리 구성
- 해당 트리를 BFS 탐색
3. 소스코드
# BFS 탐색을 위한 queue 자료구조
from collections import deque
n, k = map(int, input().split())
MAX = 100000
time = [0] * (MAX + 1) # 수빈이 0에서 100000까지의 각 거리까지의 이동 시간 기록
def bfs(start):
q = deque()
q.append(start)
while q:
x = q.popleft()
if x == k:
return
for nx in (x - 1, x + 1, x * 2):
# 범위 내이고, 아직 이동시간이 기록되지 않았을 경우
if 0 <= nx <= MAX and time[nx] == 0:
q.append(nx)
time[nx] = time[x] + 1
bfs(n)
print(time[k]) # k 위치에 기록된 이동시간 출력
4. 실패 코드
from collections import deque
n, k = map(int, input().split())
MAX = 100000
def bfs(start, time):
q = deque()
q.append((start, time))
while q:
x, t = q.popleft()
if x == k:
return t
for nx in (x - 1, x + 1, x * 2):
if 0 <= nx <= MAX:
q.append((nx, t + 1))
print(bfs(n, 0))
실패 코드이다. 큐에 현재 위치와 시간을 함께 저장하니깐 메모리 초과가 발생했다. 시간을 time list에서 따로 저장하면 time[x] == 0이 아닌 곳에는 다시 방문하지 않는데 위 코드는 방문했던 곳도 다시 큐에 push 하므로 불필요한 데이터들이 저장되어 메모리 초과가 발생한 것 같다.
Author And Source
이 문제에 관하여([BOJ] 1697번 : 숨바꼭질), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ohdowon064/BOJ-1697번-숨바꼭질저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)