난이도

Silver 1

풀이 참고 유무

X

막힌 부분

1. 방문처리하지 않고 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이므로 방문처리를 하도록 하여 메모리와 시간을 줄여보자.

풀이(python)

Python-depth 사용(오답)

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에 삽입되는 과정 때문이다.

Python - visited[] 사용(정답)

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로 똑같았다.

문제의 조건 범위를 보고 문제에 접근하자.