[BOJ] 13549 숨바꼭질 3 Python

(복습)

https://www.acmicpc.net/problem/13549

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는 정수이다.

출력

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

예제 입력 1 복사

5 17

예제 출력 1 복사

2

 

풀이(정답 참고)

import sys
input = sys.stdin.readline
from collections import deque

suvin, sis = map(int, input().split())
visited = [False]*100001
count = [0]*100001

queue = deque()
queue.append(suvin)
visited[suvin] = 0

while queue:
    x = queue.popleft()
    if x == sis:
        print(count[sis])
        break
    for i in (2, +1, -1):
        if i == 2:
            if 0<x*2<100001 and not visited[x*2]:
                visited[x*2] = True
                # 순간이동 하더라도 이전에 이동했던 횟수를 누적해줘야 한다.
                count[x*2] = count[x]
                queue.appendleft(x*2)
        else:
            nx = x+i
            if 0<=nx<100001 and not visited[nx]:
                visited[nx] = True
                queue.append(nx)
                count[nx] = count[x]+1

세달 전에 풀었던 문제인데, 역시나 정답을 참고한 문제는 다시 풀 때 완벽히 혼자 풀지 못한다.

1. 순간이동 할 때도 시간이 증가하지 않는다고 하더라도, 그 전 시간을 count에 누적해줘야 한다.

2. 곱하기 2를 먼저 해야 더 최단시간에 가까워지므로 appendleft를 해줘서 먼저 탐색하게 해줘야 한다. (아마 그래야 시간초과가 안 났던 걸로 기억)

3. 0을 곱하면 0이기 때문에 범위 주의

 

대략 이 세가지 포인트를 생각하지 못했다.

 

이전에 풀었던 것도 여러 번 다시 풀어보자 !