백준 1697번 : 숨바꼭질 in Python
위 문제는 어떤 한 점에서 다른 한 점으로 가기 위해 걸리는 최단 시간을 구하는 문제로, 이동 방법에는 앞뒤로 한 칸 또는 그 점의 좌표만큼 앞으로 이동하는 방법이 있다.
만약 뒤로 이동할 수 없었다면 dynamic programming을 이용하거나, greedy algorithm을 이용하면 매우 쉽게 풀 수 있는 문제이다. dynamic programming을 이용하는 경우 시작점과 끝점의 좌표 차이를 크기로 갖는 배열을 하나 만들고 배열의 각 원소마다 처음부터 그 원소까지 가기 위한 최소 시간을 순차적으로 구해나가면 된다. 또한 greedy algorithm을 이용하는 경우 결국에는 그 점의 좌표만큼 앞으로 이동하는 방법이 0번째 인덱스를 제외하고는 한 칸 앞으로 가는 것보다 유리하므로 이를 이용해 최대한 목적지 근처까지 가고 남은 거리를 한 칸씩 앞으로 가면 된다.
하지만 위 문제는 뒤로 가는 경우를 포함하므로 이런 식으로 풀 경우 일부 문제는 비효율적인 이동 결과가 나오게 된다. 예를 들어 5 9라는 예제가 있을 때 뒤로 가는 경우를 제외하면 5 -> 6 -> 7 -> 8 -> 9로 이동할 수밖에 없어 총 4초가 소요되지만, 뒤로 가는 경우를 포함하면 5 -> 10 -> 9로 총 2초가 소요된다. 이는 dynamic programming으로 구현하는 게 불가능하다. 왜냐하면 dynamic programming으로 배열의 인덱스마다 순차적으로 최단 시간을 구한다고 하면 해당 원소의 한 칸 앞의 최단 시간을 알아야 하는데, 이는 아직 구하지 않은 값이기 때문이다.
그래서 이 문제는 BFS를 이용해 최단 거리를 구하는 문제와 유사하게 해결해야 한다. 특히 이 문제는 어떤 인덱스와 연결된 인덱스가 해당 인덱스에서 1을 뺀 것, 1을 더한 것, 2를 곱한 것이므로 이 세 경우에 대해 연산 결과가 0~100000 사이인지 검사하고 이미 방문한 원소인지를 검사한다. 이때 방문한 원소인지는 해당 인덱스의 값이 0인지로 판단한다. 이는 배열의 인덱스에 해당하는 값을 그 인덱스에 도달하기 위해 필요한 최소 시간으로 구하기 때문이다. 최소 시간은 기준 인덱스와 인접해 있는(1초만에 바로 도달할 수 있는) 인덱스에 대해 기준 인덱스의 값에 1을 더한 값으로 한다.
그리고 이에 대한 while loop을 돌면서 queue에서 꺼낸 값이 K면 while loop을 종료한다.
이를 코드로 구현하면 다음과 같다.
from collections import deque
N, K = map(int, input().split())
# 인덱스까지 도달하는 데 걸리는 최소시간을 저장하는 배열
arr = [0 for _ in range(100001)]
queue = deque()
queue.append(N)
while len(queue) > 0:
x = queue.popleft()
# 목적지에 도달하면 while loop을 끝낸다.
if x == K:
break
# 한 칸 뒤로 이동하는 경우
if x >= 1 and arr[x-1] == 0:
arr[x-1] = arr[x] + 1
queue.append(x-1)
# 한 칸 앞으로 이동하는 경우
if x < 100000 and arr[x+1] == 0:
arr[x+1] = arr[x] + 1
queue.append(x+1)
# 해당 인덱스만큼 이동하는 경우
if x <= 50000 and arr[x*2] == 0:
arr[2*x] = arr[x] + 1
queue.append(2*x)
print(arr[K])