[백준/BOJ] gold5 - 13549번 숨바꼭질 3 (Python)

▶13549 - 숨바꼭질 3

백준 로고

▶문제

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

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

 

▶입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

▶출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

728x90

▶풀이

지난번에 풀었던 숨바꼭질 2와 아주 유사한 문제이다.

2023.03.07 - [BOJ Code/Gold] - [백준/BOJ] gold4 - 12851번 숨바꼭질 2 (Python)

[백준/BOJ] gold4 - 12851번 숨바꼭질 2 (Python)

 

출력하는 형식과 중간에 살짝 조건이 다르다.

이번에는 순간이동 하는 경우에는 시간을 쓰지 않는다.

그래서 x * 2 해줄 때는 cnt를 그대로 queue에 넣어주면 된다.

 

그 외에 구하는 과정은 거의 비슷하다.

from collections import deque


def bfs():
    queue = deque()
    queue.append([n, 0])
    visit = [0 for _ in range(100001)]
    visit[n] = 1
    while queue:
        x, cnt = queue.popleft()
        if x == k:
            return cnt
        
        if 0 <= x - 1 <= 100000 and visit[x - 1] == 0:
            queue.append([x - 1, cnt + 1])
            visit[x - 1] = 1
        if 0 <= x * 2 <= 100000 and visit[x * 2] == 0:
            queue.append([x * 2, cnt])
            visit[x * 2] = 1
        if 0 <= x + 1 <= 100000 and visit[x + 1] == 0:
            queue.append([x + 1, cnt + 1])
            visit[x + 1] = 1
    
    return -1


n, k = map(int, input().split())
print(bfs())