백준 1697번 숨바꼭질 파이썬

https://www.acmicpc.net/problem/1697

 

문제

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 <= N <= 100,000) on a number line and the cow is at a point K (0 <= K <= 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

• Walking: FJ can move from any point X to the points X-1 or X+1 in a single minute
• Teleporting: FJ can move from any point X to the point 2*X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

입력

* Line 1: Two space-separated integers: N and K

 

출력

* Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

 

예제 입력 1 복사

5 17

예제 출력 1 복사

4

힌트

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

 

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO US Open 2007 Contest > Silver 2번

• 데이터를 추가한 사람: arat5724, cohan, djm03178
• 문제를 번역한 사람: author6

728x90

import sys
from collections import deque

def bfs(v):
    q = deque([v]) #큐 구현을 위해 deque 사용
    while q:
        v = q.popleft()
        if v == k:
            return visited[v]
        for i in (v-1, v+1, 2*v):
            if 0 <= i <= 100000 and not visited[i]:
                visited[i] = visited[v] + 1
                q.append(i)

n, k = map(int, sys.stdin.readline().split())
visited = [0 for i in range(100001)]
print(bfs(n))

 

처음에는 DP 문제인가 해서 , Dynamic Programming, 으로 접근했는데

반응형

요건 

 

2배로 순간이동한 뒤 뒤로 가거나

뒤로 한칸가서 2배로 순간이동하는 등의 다양한 경우가 있기에

 

DP보다는 BFS 혹은 Branch and Bound가 더 적절하다 판단

https://tonnykang.tistory.com/226

Branch and Bound 분기 한정 알고리즘

 

그래서 Queue를 사용해 (Dequeue)

BFS를 했는데

 

처음에는 왜 BFS를 통해 찾은 첫 솔루션이 왜 최적해인지 이해가 잘 안갔지만

 

Node의 Level =  움직임의 횟수

그리고 BFS로 탐색하면

Level이 낮은 것 부터 점차점차 탐색함으로

 

가장 처음으로 발견한 솔루션이 최적해임..!

여러 최적해가 있을 수 있음 -> 같은 층에 있는 여러 솔루션 노드들

 

하지만 이런 트리 탐색 알고리즘은 시간복잡도가 굉장히 커질 수 있기에...
이 경우에는 3제곱으로 늘어남

조심해야한다

 

https://tonnykang.tistory.com/153

[백준,C++] 18111번 : 마인크래프트