[백준/파이썬] 13549번 숨바꼭질 3 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 13549번 숨바꼭질 3
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

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

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

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

from collections import deque

MAX_POS = 101_762

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

q = deque([(n, 0)])
push_right = q.append
push_left= q.appendleft
pop = q.popleft
visited = [MAX_POS]*MAX_POS
visited[n] == 0

answers = []

while q:
    pos, time = pop()
    if pos == k: answers.append(time)

    if pos * 2 < MAX_POS and visited[pos * 2] > time:
        visited[pos * 2] = time
        push_left((pos * 2, time))
        
    if pos + 1 < MAX_POS and visited[pos + 1] > time + 1:
        visited[pos + 1] = time + 1
        push_right((pos + 1, time + 1))
        
    if 0 < pos and visited[pos - 1] > time + 1:
        visited[pos - 1] = time + 1
        push_right((pos - 1, time + 1))


print(min(answers))

설명

BFS를 사용하면 쉽게 풀 수 있습니다.

단, 순간이동시에는 0초가 소모되므로, 순간이동시에는 이를 뒤쪽에서 넣는 게 아니고, 앞쪽에서 넣어줘야 합니다. 따라서, 일반적인 큐로는 풀 수 없습니다.

양쪽을 모두 출입구로 쓸 수 있는 데크를 응용하면 쉽습니다.

MAX_POS의 경우 순간 이동 후 왼쪽으로 갈 때 문제에 주어진 동생의 위치의 최댓값(100,000)보다 큰 상태에서 가는 경우가 빠를 수 있으므로, 확실하게 100,000보다는 커야 합니다. 정확한 최솟값은 계산을 하면 쉽게 구할 수 있겠지만, 귀찮아서 여러번 제출해보며 통과된 코드 중 실행 시간이 가장 짧게 나온 수로 정했습니다.

---

• 백준 문제풀이 전체 목록 보기

---