[BOJ] 13549. 숨바꼭질 3 (python)

✏️ 문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

🤖 알고리즘

 

#BFS 

 

 

🤯 풀이 방법

 

기본적인 BFS 문제.. 인데 예외처리가 많았던 문제

시간을 구해야 하는데 시간이 여러 경우가 있기 때문에 시간이 적은 0초부터 큐에 넣도록 해야 한다.

범위 확인을 안 하고 돌렸더니 메모리초과 나서 visited 체크를 하고, 

-1과 *2 가 있기 때문에 visited 범위 초과로 indexError가 나서 그 부분도 체크해줬다.

 

👾 구현 코드 (파이썬)

# [BOJ] 13549. 숨바꼭질 3
import sys
input = sys.stdin.readline
from collections import deque


# 최소값 찾기: BFS 사용
def bfs(N):
    v = [0 for x in range(100001)]
    q = deque()
    q.append([N, 0])
    v[N] = 1  # visited 체크 안 하면 메모리 초과

    while q:
        c = q.popleft()
        if c[0] == K:  # K에 도착하면 현재까지의 시간 리턴
            return c[1]

        # 순간이동이 0초로 빠르므로 먼저 순회          
        d = [c[0] * 2, c[0] - 1, c[0] + 1]
        for i in range(3):  # 3개의 경우의 수 (+1, -1, *2)
            # if문에서 인덱스 체크 먼저 -> visited 체크 먼저 할 시 indexError
            if i == 0 and 0 <= d[i] <= 100000 and v[d[i]] == 0:  # 순간이동하는 경우
                v[d[i]] = 1
                q.append([d[i], c[1]])
            elif i in [1, 2] and 0 <= d[i] <= 100000 and v[d[i]] == 0: 
                v[d[i]] = 1
                q.append([d[i], c[1] + 1])  # 1초가 소요되므로 소요시간에 1 추가
  

# N: 수빈이, K: 동생의 위치
N, K = map(int, input().split())
print(bfs(N))

13549번: 숨바꼭질 3