백준 13549: 숨바꼭질 3 (Python)

문제

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

해설

BFS 또는 다익스트라 알고리즘을 활용해 풀 수 있는 문제다. 이 풀이에서는 BFS를 활용해 문제를 풀었다.

 

• 기본적으로 BFS로 모든 이동방법에 대해 탐색해주어야 한다.
• 이동 방법에는 3가지가 존재한다.
  • X-1 로 이동하기 (1초)
  • X+1 로 이동하기 (1초)
  • 2*X 로 순간이동하기 (0초)
• 각 이동 방법에 대해 큐에 넣어가면서 위치, 지금까지의 이동시간을 기록한다.
  • Q.append([다음 위치, 이동시간])
  • 현재 위치, 이동시간 = Q.popleft()
• 만약 현재 위치가 Y인 경우 정답을 출력하고 루프를 종료한다.
  •     if x == K:
            print(t)
            break
• 이때, 순간이동으로 움직이는 경우 소요되는 시간은 0초이기 때문에 제일 효율적이다.
• 그러므로 순간이동을 우선적으로 검사해주어야 함에 유의하자
  • for action in [[2*x, 0], [x-1, 1], [x+1, 1]]: # 순간이동을 우선적으로

 

 

코드

from collections import deque


N, K = map(int, input().split())

visited = [False] * 100001
Q = deque()
Q.append([N, 0]) # [위치, 초]
visited[N] = True

while Q:
    x, t = Q.popleft()
    
    if x == K:
        print(t)
        break
    
    for action in [[2*x, 0], [x-1, 1], [x+1, 1]]: # 순간이동을 우선적으로
        tx, tt = action
        
        if tx < 0 or tx > 100000:
            continue
            
        if not visited[tx]:
            visited[tx] = True
            Q.append([tx, t+tt])