[Algorithm] 백준_13349번: 숨바꼭질3

드디어 오늘의 문제는 🚀 백준 13539 숨바꼭질3 이다.

이것도 숨바꼭질과 비슷하지만, *2가 순간이동이기 때문에 시간이 걸리지 않는다…!

테스트케이스 이해하기

이것도 수빈이랑 동생이랑 숨바꼭질을 해서, 수빈이가 찾으러 가는 것이다.

이동할 수 있는 방법은 +1, -1, *2 방법이 있고,

+1, -1 씩 이동할때는 1씩 시간이 걸리지만, *2 은 순간이동이여서 시간이 걸리지 않는다.

그럼 가장 시간이 짧게 걸리는 방법은 무엇인가?

알고리즘

기본 알고리즘은 숨바꼭질이랑 비슷하다.

1. 방문했는지 확인하는 check, 각각 거리가 얼마인지 저장하는 dist를 선언한다.

2. deque를 이용해서 수빈이의 위치를 넣고, while문을 시작한다.

3. 세가지 경우로 나눠서 범위를 확인을 해야 한다.

   1. *2 만큼 이동했을 경우는 시간이 걸리지 않기 때문에 q.appendleft를 사용해서 앞에다가 넣어준다.
   2. +1, -1, 만큼 이동했을 경우는 그대로 q.append를 사용한다.
   3. *2는 dist를 이전과 를 똑같이 넣어주고 +1, -1 은 dist를 1씩 늘려서 채운다.
   4. 방문했기 때문에 check도 1로 업데이트 하준다.

4. 현재 위치가 수빈이 동생 위치이면 프린트 하고 break 해서 탈출!

   
   

• *2의 경우만 appedleft를 사용하는 이유

  BFS는 자신으로 부터 같은 거리에 떨어져 있는 곳을 다 방문해야 다음 거리에 떨어져 있는 정점에 방문한다.

  그래서 주로 최단 거리를 구할때 주로 사용하는데, 이때 무조건 가중치가 같아야 한다.

  하지만 가중치가 딱 두개일 경우,

  • queue를 두개를 사용해서 BFS로 풀기
  • 덱을 사용해서 BFS로 풀기가 있다!

  queue를 두개 사용할 경우는 가중치에 따라 각각 큐에 넣어주면 되고,

  덱을 사용할 경우에는 앞에다가 넣어주면 큐를 두개 사용한 것과 같다!

  그래서 *2는 가중치가 0이기 때문에 이동을 했음에도 이전단계와 같은 레벨이기 때문에 앞에다가 넣어준다.

  
  

• 해결하지 못한 점

  *2 케이스를 맨 뒤에 넣으면 백준을 통과하지 못한다..!

  이유가 뭘까? 이것 때문에 한시간을 날렸는데 아직 해결하지 못하였다…ㅠㅠ

정답코드

from collections import deque
max=200000
a,b = map(int,input().split())
check=[False]*max
dist=[0]*max

q = deque()
q.append(a)
check[a] = True

while q:
    now = q.popleft()
    if now ==b:
        print(dist[b])

    if -1< now*2 < max:
        if not check[now * 2]:
            q.appendleft(now*2) #앞으로 넣어준다.
            check[now * 2] = True
            dist[now * 2] = dist[now]

    if -1< now +1 < max:
        if not check[now+1]:
            q.append(now+1)
            check[now+1] = True
            dist[now+1] = dist[now]+1

    if -1< now-1 < max:
        if not check[now - 1]:
            q.append(now - 1)
            check[now - 1] = True
            dist[now - 1] = dist[now] + 1

🚀Reference: 백준 13539 - 숨바꼭질3