수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
- 입력
- 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
- 출력
- 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17
예제 출력 1
4
걷는다면 1초 후에 X-1 또는 X+1로 이동하고,
순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
그래서 5에서 17로 가기 위해서는 5 -> 10 -> 9 -> 18 -> 17 총 4번 이동하게 된다.
n, k = map(int, input().split())
먼저 n,k를 input으로 받고,
일단 bfs, dfs 생각 안하고 코드를 짜봤다.
count = 0
while n!=k:
if abs(n*2-k)<=abs(n-1-k): n*=2
else:
if n>k: n-=1
else: n +=1
count+=1
print(count)
이렇게 하면, 5-> 10 -> 20 -> 19 -> 18 -> 17 이런 경로로 진행하게 되어 5가 출력된다.
일단 이 문제가 왜 DFS, BFS 인지 생각해봤다.
아마도 걸을때는 같은 level의 node가 되고, 순간이동할 때에는 child node로 한칸 이동한다는 걸까 싶기도 하고,,,
맨날 이렇게 막히는 단계에서 그냥 다른 분들 코드를 봐버리는데 이번엔 좀 더 고민해보기로 @@
그리고 계속 고민하다가 진짜 감이 안잡혀서 살짝 구글링해서 딱! BFS 문제라는 거 까지만 알아냈다
그래서 이번엔 BFS로 접근하기로 했다.
limit = 100000
visited = [0] * (limit+1)
BFS니까 임의의 큰 수로 visited도 만들고, 0으로 채웠다. 한번 방문한 곳은 방문하지 않아야 하니까!
queue = [[n,0]]
while queue:
temp = queue.pop(0)
v = temp[0]
count = temp[1]
if v == k:
print(count)
break
visited[v] = 1
if v*2<limit and visited[v*2] == 0: queue.append([v*2, count+1])
if v+1<limit and visited[v+1] == 0: queue.append([v+1, count+1])
if v-1<limit and i>0 and visited[v-1] == 0: queue.append([v-1, count+1])
결국 다른 분들의 코드를 조금 참고해서 코드를 마무리했다 ㅠㅠ
이 문제의 포인트는, queue에 [locate, count] 의 element를 입력해줘야 한다는 것 !
그리고 limit라는 범위를 지정해서 v*2나 v+1, v-1이 0이상 limit 이하인지 확인하는 것!
그 결과 예시 입력을 넣으면, sum(visited)가 29이 나오는 것을 알 수 있다!
비슷한 BFS문제를 더 풀어봐야겠당