[백준 13913번] 숨바꼭질 4

mokomoko·2022년 2월 3일

1. 문제

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

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

제한 사항

시간 : 2 초
메모리 : 512 MB

입력

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

출력

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

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

- 키워드

탐색을 할 때는 BFS와 Cache를 같이 쓰도록 하자.

역추적을 할 때는 Stack을 사용하자.

2. 풀이

처음에 이 문제를 풀었을때 시간적 효율 상승을 위해 PriorityQueue로 접근하려 했으나,

반례가 많아서 정석적으로 Queue를 사용해 BFS를 사용했다.

예제 테스트케이스를 다음으로 해보자.

10 38

1. 탐색

Queue에 10을 삽입하고 시작한다.

Queue에서 10을 Dequeue하고 계산을 한다.

10을 통해 나올 수 있는 값은 다음과 같다.

10+1, 10-1, 10*2

cache에 1번째 방문이라는 의미로 1을 저장하고 Queue에 넣는다.

계산 중간에 K값에 방문했는지 체크하면서 하도록 한다.

11을 통해 나올 수 있는 값은 11+1,11-1,11*2

9를 통해 나올 수 있는 값은 9+1,9-1,9*2

20을 통해 나올 수 있는 값은 20+1,20-1,20*2

그런데, 여기서 10은 방문하였으므로 11-1,9+1은 제외하고 Queue에 저장한다.

두 번째 방문이므로 cache에는 2를 저장한다.

이와 같은 방식으로 탐색을 진행하면 된다.

너무 사이즈가 커지므로 탐색은 여기까지만 설명하고 역추적을 해보자.

2. 역추적

K에 도착했다면, stack에 K를 삽입하고 시작하자.

과정을 문제 없이 잘 거쳤다면 cache에는 다음과 같이 저장이 되었을 것이다.

총 3번의 연산을 통해 도달하였고, 그 전과정을 탐색해보자.

연산은 N+1,N-1,N*2 이므로, 반대로 가려면

N-1,N+1,N//2를 해야 한다.

주의 해야 할 점은 특정 케이스에서 IndexError를 일으킬 수 있으므로, 예외 처리를 잘 하도록 하자.

38에서 역추적을 하면 37,39,19이다.

이전 경로에 해당되는 값은 19뿐이므로, 19를 스택에 넣어준다.

19에서 이전 경로 후보로 올 수 있는 것은 18,20이다.

19는 홀수 이므로 N//2를 할 수 없다.

이전 경로에 해당되는 값은 20이므로, 20을 스택에 넣어준다.

20에서 이전 경로 후보로 올 수 있는 것은 19,21,10이다.

이전 경로에 해당되는 값은 10이므로, 10을 스택에 넣어준다.

Stack의 Top이 N이랑 같으므로 탐색을 종료한다.

해당 테스트케이스에서는 나오지 않았지만, 만약 이전 경로 후보 중 이전 경로에 해당되는 값이 없다면

Stack에서 pop을하고 그 위치를 INF로 초기화하고 다시 탐색한다.

3. 소스코드

import sys
from collections import deque
INF = float('inf')
input = sys.stdin.readline

def solution(N,K):
	field = [INF] * 100001
	field[N] = 0
	q = deque()
	q.append(N)
	while q:
		now = q.popleft()
		if now-1 >= 0 and field[now-1] == INF:
			q.append(now-1)
			field[now-1] = field[now]+1
		if now+1 < 100001 and field[now+1] == INF:
			q.append(now+1)
			field[now+1] = field[now]+1
		if now*2 < 100001:
			if field[now*2] == INF:
				q.append(now*2)
				field[now*2] = field[now]+1
		if field[K] != INF:
			break

	stack = [K]
	while stack[-1] != N:
		now = stack[-1]
		if now-1 >= 0:
			if field[now-1]+1 == field[now] and now == stack[-1]:
				stack.append(now-1)
		if now+1 < 100001:
			if field[now+1]+1 == field[now] and now == stack[-1]:
				stack.append(now+1)
		if field[now//2]+1 == field[now] and now % 2 == 0 and now == stack[-1]:
			stack.append(now//2)
		if now == stack[-1]:
			field[now] = -100
			stack.pop()
	print(field[K])
	while stack:
		print(stack.pop(),end=" ")

if __name__ == "__main__":
	N,K = map(int,input().split())
	solution(N,K)