BOJ 13549. 숨바꼭질 3 (파이썬 Python)

 

Solved.ac 기준 🥇 골드 5

문제

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

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

 

입력

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

출력

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

 

 

문제 풀이

문제에서 주는 조건이 기존에 숨바꼭질과는 다른점이 있다. 원래 위치의 이동은 다 1초로 통일되어있었는데, 여기선 앞 뒤 움직임만 1초가 소요된다고 나온다. 즉 순간이동을 할 때는 시간이 소요되지 않는다는 말이다. 이 점만 잘 구현해주면 된다고 생각했다.

 

처음엔 이 시리즈의 이전 문제의 로직을 따라 했었다. x-1,x+1, x*2 를 하나로 묶어서 for문을 돌렸지만, 답은 잘 나오지 않았다.

 

그러다 여러 블로그를 돌며 로직을 파악했고, 답을 도출했다.

 

일단 예시 문제를 푸는 과정을 살펴봤다. 

 

예시 문제의 input은 5 , 17 .

이 문제를 수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다. 로 푸는 힌트를 보며, 먼저 곱하고 앞 뒤로 빼는 로직이 맞겠구나 라는 생각을 해냈다. 따라서 한번에 다 하는게 아닌, 먼저 곱하고 앞 뒤로 빼주는 걸 구상했다.

 

# 숨바꼭질 3
import sys
from collections import deque
input = sys.stdin.readline
n,k = map(int,input().split())
MAX_INDEX = 100000
board = [-1] * (MAX_INDEX+1)
#dist = [False] * (MAX_INDEX+1)
q = deque()
q.append(n)
board[n] = 0
#dist[n] = True
while q:
    x = q.popleft()
    if x == k:
        break
    if x * 2 <= MAX_INDEX and board[x*2] == -1: #dist[x*2] == False:
        q.append(x*2)
        board[x*2] = board[x]
        #dist[x*2] = True
    
    for nx in (x-1, x+1):
        if 0 <= nx <= MAX_INDEX and board[nx] == -1: #dist[nx] == False:
            q.append(nx)
            board[nx] = board[x] + 1
            #dist[nx] = True
print(board[k])

 

주석처리의 의미는 , dist 리스트를 만들어 이게 방문을 했었는지 안했었는지를 판단하는 리스트이다.

근데 생각을 다시 해보니, 굳이 dist가 필요 없고, 초기 설정을 해논 board의 값이 만일 바뀌었으면 지나간 것이니, 그 값으로 dist의 역할을 대체했다. 

 

코드를 보면, 먼저 인덱스를 뽑아서 2를 곱해주고, 그다음에 for문을 돌아가는 형식으로 꾸며졌다.

 

아래의 맞았습니다는 dist 리스트를 활용한 것, 위에 꺼는 없앤것이다. (속도차이는 별로 없었다..)