[백준,Python]1697번 숨바꼭질(BFS)

백준 1697번: 숨바꼭질 문제를 리뷰하는 시간을 가져보겠습니다.

문제를 요약하면,

-N과K 두 수를 입력 받아 N이 K에 도달하는 최단 시간을 구하는 문제이고, N은 1초에 +1,-1,*2방법을 통해 이동할 수 있습니다. (자세한 문제 설명은 https://www.acmicpc.net/problem/1697를 참고하시면 됩니다.)

 

먼저, 이 문제는 BFS로 푸는 문제이며, DFS와의 차이에 대해서 간략하게 설명드리겠습니다. 

DFS는 탐색하면서 depth가 증가할 때 마다, 기준점을 바꾸고 재귀를 써서 탐색을 진행하게 되는데, 이 문제를 그렇게 풀 경우 무한 루프에 빠지므로 BFS로 푸는 방식을 이용해 탐색을 진행하도록 구현하였습니다.

 

DFS로 풀지 않고 BFS로 푼다의 가장 큰 특징은 for문 또는 while문을 사용하여 답을 찾을 때까지 반복하며 조건문을 활용해 비교하면서 풀도록 구현하는 것입니다. 

 

from collections import deque
n,k = map(int, input().split()) # 

MAX = 100001
dp = [MAX]*MAX # dp는 찾아가는 방법을 count하여 저장한 리스트이며,정답을 출력할 때 dp[num]으로 활용할 것이다.
dp[k] = 0 #k를 기준점으로 n을 찾아가는 방식을 이용함.

queue = deque()
queue.append(k)

while queue:
    num = queue.popleft()
    if num ==n:
        print(dp[num])
        break
    if num < MAX - 1 and dp[num + 1] > dp[num] + 1: #dp의 모든 리스트값을 MAX값으로 설정해줬기에 방문하지 않은 점으로만 방문할 수 있게 된다.
        dp[num + 1] = dp[num] + 1
        queue.append(num + 1)
    if num > 0 and dp[num - 1] > dp[num] + 1:
        dp[num - 1] = dp[num] + 1
        queue.append(num - 1)
    if num % 2 == 0 and dp[num // 2] > dp[num] + 1:
        dp[num // 2] = dp[num] + 1
        queue.append(num // 2)

-deque는 스택과 큐의 기능을 모두 가진 객체로 양쪽 출입구가 있어 편리하게 사용할 수 있습니다. 

 

-queue.Queue같은 경우는 멀티쓰레드를 사용할 때 사용하는 경우로 매우 느리므로, collections.deque를 사용해야 합니다.

 

-원리를 간단하게 설명하자면=>

 17을 넣었을 경우, queue에는 18 | 16 저장이 되고 depth는 1이다. 다음 경우 18을 popleft를 해주고 depth를 1증가시키고, 19,9를 append하게 된다. 다시 순서대로 16을 popleft하게 되고 15,8를 append하게 된다. 이렇게 popleft를 하게 됨으로써, 같은 depth있는 value를 우선으로 탐색을 진행하게 됨으로 BFS라고 할 수 있습니다.