BOJ-1697 숨바꼭질

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

문제 소개

현재 위치가 x라고 했을 때, x - 1 또는 x + 1 또는 x * 2의 위치로 이동할 수 있으며, 한 번의 이동에 1초가 걸린다.

n과 k가 주어졌을 때, n에서 k로 이동하는 가장 빠른 시간이 몇 초인지 구하는 문제이다.

문제 풀이

n과 k의 값에 따라 3가지 경우로 나누어 생각하였다.

1. n < k : bfs로 최소 시간을 계산한다.
2. n > k : 단순히 n - k를 계산한다.
3. n == k : 정답은 0이 된다.

1번 경우의 풀이에서 사용된 변수들은 아래와 같다.

• max : n과 k의 최대값
• acc : n에서 각 인덱스의 위치까지 가는데 걸리는 최소 시간을 담는 리스트
• limit : 반복 과정에서 불필요한 연산을 하지 않기 위해 큐에 append하는 위치값을 0부터 limit까지 제한하도록 사용하였다. 값이 min(max, k + 1)인 이유는 k의 값에 도달하는 과정 중 가장 커질 수 있는 수가 k + 1인 동시에 최대값이 max로 제한되었기 때문이다.

해답은 bfs로 찾게된다. 현재 위치에서 이동 가능한 위치 중 가용한 범위 내에 있으며 값이 갱신되는 경우 위치값을 큐에 append하는 동시에 이동 시간에 1을 누적한다.

만약 조건을 만족하는 위치가 k에 도달한 경우 이동 시간을 출력하고 프로그램을 종료한다.

코드

from collections import deque


def bfs(x):
    queue = deque([x])
    acc[x] = 0
    limit = min(max, k + 1)
    while queue:
        t = queue.popleft()
        for i in [t - 1, t + 1, t * 2]:
            if 0 <= i <= limit and acc[t] + 1 < acc[i]:
                acc[i] = acc[t] + 1
                if i == k:
                    print(acc[i])
                    exit()
                # print(f"acc[{i}] : {acc[i]}")
                queue.append(i)


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

if n < k:
    max = 100000
    acc = [max] * (max + 1)
    bfs(n)
elif n > k:
    print(n - k)
else:
    print(0)

주석 처리된 print문으로 큐에 추가되는 위치에 대한 정보를 확인할 수 있다.