문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입출력
접근
이 문제의 접근 아이디어는 다음과 같다.
1. 그래프로 판단
수빈이의 위치 값을 노드로 생각해보자.
그렇다면, 입력으로 주어진 수빈이의 위치n은 시작노드가 될것이고, 1초뒤에 이동을 다음노드로 가는데 간선의 가중치가 1이다라고 생각할수 있다.
인접노드는 현재 노드에 +1,-1,*2한 값이 될것이다.
2. 그래프 탐색
그래프를 미리 만들지 않고, bfs탐색을 하면서 인접노드를 큐에 추가할때 인접노드를 만들어나가는 식으로 탐색을 해서, 시간을 줄여본다.
인접노드를 생성하고 큐에 넣을 때는 계산된 가중치 값을 같이 넣어서, 목표에 도달한 노드가 나오면 해당 가중치를 출력한다.
노드값이 같더라도, bfs로 탐색하기 때문에 가장 먼저 나온값이 가중치가 적다.
따라서 목표값인 노드를 찾으면, 곧바로 탐색을 종료하고 저장하고 있는 가중치를 출력해준다.
3. 예외들 처리
우선, 현재위치와 목적지가 같으면 이동할필요가 없으니까 0을 출력해준다.
그 다음으로 메모리 오류를 처리해줘야 한다.
위의 방식으로 코드를 짜면 메모리 초과가 난다.
동생의 위치(목적지)는 최대값이 10만이다.
인접노드를 추가할때 10만을 넘지 안도록 해서 메모리 초과가 나지 않도록 해야 한다.
이를 제한하지 않으면 추가할 노드가 너무 많아진다.
예를 들어 *2를 해서 18만이 되었다고 하자.
나누기가 없기 때문에 목표지점까지 오려면 최소 8만번을 1씩 빼줘야 한다.
즉, 노드가 8만개가 생길수도 있다는 것이다.
코드는 다음과 같다
import sys
from collections import deque
'''입력'''
#n:수빈이의 위치(탐색 시작 노드값), 동생의 위치(최종 목적지 값)
n,k = map(int,sys.stdin.readline().split())
#시간초과 안나도록 크기 제한 - 주어진 크기가 10만이므로 이를 안넘도록 함.
max = 100000
# 시작, 끝값을 받고 목적지 도달에 걸린 시간 프린트
#걸린 시간 카운트
count = 0
#key 값에 노드, value에 걸린 시간을 저장.
visited = dict()
need_visited = deque(list())
need_visited.append([n,0])
visited[n] = 0
while need_visited:
current_node , current_count = need_visited.popleft()
#목적지 노드이면 count에 걸린시간 저장하고 반환 - 큐에 넣어서 탐색하기 때문에 가장 먼저 도달하는게 최소시간임
if current_node == k:
count = current_count
break
next_node_list = [current_node - 1,current_node + 1,current_node * 2]
for next_node in next_node_list:
#저장된 값이 없으면 추가
if next_node not in visited:
if next_node <= max:
visited[next_node] = current_count+1
need_visited.append([next_node,current_count+1])
print(count)
결과
