백준-1697-숨바꼭질

문제

숨바꼭질

풀이

1. 문제조건 해석

   N에서 M 도달하는 최소 시간 문제다.

   문제조건만 보고 dp로 풀어야 할 줄 알았다.

   그러나, dp는 m에 도달하는 모든 경우($O(3^n)$)를 비교해봐야 하므로 시간초과 난다.

   BFS를 이용해서 시간순으로 m에 먼저 도달하게 되면 break해야 하는 문제다.

2. 알고리즘

   • dp로 풀면 실패한다.
   • BFS로 한번 순회 당 (<3)개의 경우의 수 추가된다.
   • 큐에 넣기 전 visited 확인해야 함
   • 범위 내로 최적화하지 않으면 음수값까지 넘어가서 메모리 초과 일어남

3. 코드

    from collections import deque
    n, k = [int(x) for x in input().split()]
       
    queue = deque([n])
    step = 0
    visited = {n:step}
    while queue:
        step += 1
        for _ in range(len(queue)):
            pos = queue.popleft()
            if pos == k: # 반복문 중단.
                visited[k] = step-1
                queue = None
                break
            if pos <= k and pos+1 not in visited:
                visited[pos+1] = step
                queue.append(pos+1)
            if pos > 0 and pos-1 not in visited:
                visited[pos-1] = step
                queue.append(pos-1)
            if pos <= k and 2*pos not in visited:
                visited[2*pos] = step
                queue.append(2*pos)
    print(visited[k])
   

4. 배운점

• 메모리 초과가 많이 일어났다. 가능한 경우의 수 최대로 줄이는 최적화를 잘 생각해야 한다.
• 최소 시간 문제는 dp뿐만아니라 BFS로 풀어야 할 경우도 있다.
• 관련 문제
  • 1로 만들기