Silver 1
X
- 방문처리하지 않고 depth로 답을 구하려해서 메모리 초과
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
5 17
4
x-1, x+1, 2*x 방향으로 넓게 탐색할 수 있다.
단 n이 100,000이므로 방문처리를 하도록 하여 메모리와 시간을 줄여보자.
from sys import stdin
from collections import deque
def BFS(x,depth):
q=deque()
q.append((x,depth))
while q:
su,depth=q.popleft()
if su==k:
print(depth)
break
if su>0:
q.append((su-1,depth+1))
if su<100000:
q.append((su+1,depth+1))
q.append((2*su,depth+1))
n,k = map(int,stdin.readline().split())
# visted=[0 for _ in range(100001)]
BFS(n,0)
위 풀이로는 낮은 범위에 조건이 주어지면 답을 구해내지만 높은 범위가 주어지면 연산이 너무 오래걸린다.
백준 채점에서는 메모리 초과로 오답처리가 된다.
계속해서 가지처럼 q에 삽입되는 과정 때문이다.
from sys import stdin
from collections import deque
def BFS(x,depth):
q=deque()
q.append(x)
if n==k:
print(0)
return
while q:
su=q.popleft()
move=[su+1,su-1,2*su]
if su==k:
print(visited[su])
break
for m in move:
if m<0 or m>100000:
continue
if not visited[m]:
q.append(m)
visited[m]=visited[su]+1
n,k = map(int,stdin.readline().split())
visited=[0 for _ in range(100001)]
BFS(n,0)
위 풀이는 방문하지 않은 곳에만 append를 해준다.
방문 횟수가 계속 누적되면서 결국에는 최적의 해를 얻을 수 있게된다.
51:44
메모리 초과가 났고 그 이유를 찾는데 시간이 오래 걸렸다.
방문처리 코드로 처음부터 수정했고 접근방식은 BFS로 똑같았다.
문제의 조건 범위를 보고 문제에 접근하자.