[백준] 1697번 숨바꼭질 아니 DP로 풀 수 없어. 이건 BFS야

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

1697번: 숨바꼭질

 

DP로 풀려다가 도저히 범위를 잡지 못해서 .. 놔줌 ㅠ

# BOJ_1697
# 입력
me, sister = map(int, input().split())

dp[1] =

dp[x] = dp[x//2] + 1

#
# # 최소 시간 찾기
# root_count = 0
# root_sister = sister
# while root_sister > me:
#     root_sister = int(sister ** (1/2))
#     root_count += 1
#     print(root_sister, root_count)
# difference = abs(root_sister - me)
# if difference > abs(root_sister ** 2 - me):
#     difference = abs(root_sister ** 2 - me)
#     root_count -= 1
#
# print(root_count, difference)
# """
# sister = me * 2 ** x + y
# y =  - a * 2 ** x + b
# x + y = t의 최솟값
# x = - y + t
# y = -a * 2 ** (-y + t)
# 워워
# """

 

dp[x]를 기준으로 1초에 나올 수 있는 상황은 다음과 같이 3가지겠지 dp[x + 1] + 1 dp[x // 2] + 1 dp[x - 1] + 1 이 3가지 중에 가장 최솟값을 구하는거야. 즉, min(dp[x + 1], dp[x // 2], dp[x - 1]) + 1 이 답이 될거야 x가 짝수 일 때  min(dp[x + 1], dp[x // 2], dp[x - 1]) + 1 x가 홀수 일때 min(dp[x + 1], dp[x - 1]) + 1

주룩.. 

 

결국 다른 사람 풀이를 보았다.

 

# BOJ_1697
from collections import deque


def bfs():
    q = deque()
    q.append(me)
    while q:
        x = q.popleft()
        if x == sister:
            return(pos_time[x])
        for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx <= max and not pos_time[nx]:
                pos_time[nx] = pos_time[x] + 1
                q.append(nx)
            

# 입력
me, sister = map(int, input().split())
max = 10 ** 5 # 시간 초과 안 나오도록 수를 제한해준다.
pos_time = [0] * (max + 1) # 각 위치별로 걸리는 시간을 보여준다.
print(bfs())

예시를 사용해볼까

참고로 popleft는 deque의 오른쪽 요소부터 꺼내준다.

 

나: 5 동생: 17

1초 소요된 거리

q = [5]

post_time[4, 6, 10] = 1

 

2초 소요된 거리

q = [4, 6, 10]

4에 대해서 post_time[3, 5, 8] = post_time[4] + 1 = 2

q = [6, 10, 3, 5, 8]

6에 대해서 post_time[5, 7, 12] = 2

q = [10, 3, 5, 8, 5, 7, 12]

10에 대해서 post_time[9, 11, 20] = 2

q = [3, 5, 8, 5, 7, 12, 9, 11, 20]

 

3초 소요된 거리

q = [3, 5, 8, 5, 7, 12, 9, 11, 20]

3에 대해서 post_time[2, 4, 6] = 3

q = [5, 8, 5, 7, 12, 9, 11, 20, 2, 4, 6]

 

5에 대해서 post_time[4, 6, 10] = 3

q = [5, 8, 5, 7, 12, 9, 11, 20, 2, 4, 6, 4, 6, 10]

 

8에 대해서 post_time[7, 9, 16] = 3

q = [5, 8, 5, 7, 12, 9, 11, 20, 2, 4, 6, 4, 6, 10, 7, 9, 16]

 

5에 대해서 

....

 

9에 대해서 post_time[8, 10, 18] = 3

q = [11, 20, 2, 4, ... , 8, 10, 18]

...

 

4초 소요된 거리

...

16에 대해서 post_time[15, 17, 32] = 4

q = [ ... , 15, 17, 32]

...

 

x = 17이 되고

if 17 == sister: 가 성립되므로

return(post_time[17])

즉, 4가 출력된다.

 

참고: https://wook-2124.tistory.com/273