[BOJ][⚪1][백준#01697] 숨바꼭질

문제 출처

BAEKJOON Online Judge #1697

문제

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

입력

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

출력

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

예제

입력

5 17

출력

4

My Sol

def bfs(N, K):
    global pos
    Q = [N]
    pos[N] = 0
    front = -1
    time = 1
    while pos[K] == -1:
        front += 1
        now = Q[front]
        if now > 0 and pos[now-1] == -1:
            pos[now-1] = pos[now]+1
            Q.append(now-1)
        if now < 10**5 and pos[now+1] == -1:
            pos[now+1] = pos[now]+1
            Q.append(now+1)
        if now <= 5*(10**4) and pos[now*2] == -1:
            pos[now*2] = pos[now]+1
            Q.append(now*2)
        time += 1
    return pos[K]

pos = [-1]*100001
N, K = map(int, input().split())

# 1. K가 N보다 작거나 같은 경우
if K <= N:
    print(N-K)
    quit()

# 2. K가 N보다 큰 경우
print(bfs(N, K))

BFS의 Queue를 이용해서 해결했다. 거리와 좌표에 대해서 어떻게 지정할까 고민했는데, 10만정도의 크기이므로 배열과 인덱싱을 이용해서 해시처럼 사용하면 편하겠다고 생각이 들었다.

Queue에 처음에 수빈이의 위치인 N을 담고, Queue에서 하나씩 꺼내어 인덱스를 채우는 것이다. 다만 이전 과정에서 채웠다면 그것이 가장 빠르게 도달할 수 있는 시간이므로 이를 체크해서 값이 채워졌다면 다음 탐색으로 넘어가야한다.

인덱스를 사용하기 때문에 Queue에서 꺼낸 현재 좌표에서부터 이동하고자 하는 좌표가 인덱스를 넘어서지는 않는지 경계설정을 하는 것이 중요하다.

결과

맞았습니다!!