13913 숨바꼭질 4 (BFS 역추적)

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

1.접근

bfs역추적을 방문했던곳인지 확인하는 check배열을 만들어  바로 전 값을 저장하도록 해서 추적하게 했다.

2.풀이

출발지점에서 도착지점까지 가는 +1,-1,*2의 3가지 뿌리로 bfs를 만들어준다. 여기서 방문했던 곳인지 확인하는 check 배열을 -1로 초기화 시킨다.bfs를 통하여 방문할때마다 cnt대신에 자신의 바로 전 위치를 집어 넣어주면 -1도 아니게 되고 어떤 경로로 현재 지점에 와있는지 알 수 있게된다.

따라서 큐에서 도착지점 값이 나올 때 cnt값을 반환하고 도착지점에서부터 시작지점까지 check배열을 순서대로 거꾸로 따라가보면 어느 경로로 왔는지 나온다.(마지막 while 문)

3.코드

	import sys
	from collections import deque
	a,b=map(int,input().split())
	check=[-1]*(100001)
	check[a]=0
	def bfs(a,b):
	Q=deque([a])
	cnt=1
	while Q:
	for _ in range(len(Q)):
	temp=Q.popleft()
	if temp+1<100001:
	if check[temp+1]==-1:
	check[temp+1]=temp
	if temp+1==b:
	return cnt
	Q.append(temp+1)
	if temp-1>=0:
	if check[temp-1]==-1:
	check[temp-1]=temp
	if temp-1==b:
	return cnt
	Q.append(temp-1)
	if 2*temp<100001:
	if check[2*temp]==-1:
	check[2*temp]=temp
	if temp*2==b:
	return cnt
	Q.append(2*temp)
	cnt+=1
	if a==b:
	print(0)
	print(a)
	else:
	temp=bfs(a,b)
	print(temp)
	ans=[b]
	while check[b]!=a:
	ans.append(check[b])
	b=check[b]
	ans.append(a)
	print(*ans[::-1])

view raw 13913숨바꼭질 (역추적).py hosted with ❤ by GitHub

4.배운점

• 처음에 check배열에 cnt값을 넣는게 습관화되어서 역추적을 할 때 함수를 또 만들어서 bfs를 돌리느라 시간과 코드가 커졌다, check배열에 바로 전의 값을 넣어주면 추적하기 쉬워지는걸 배웠다.
• DSLR문제도 11779번 최소비용 구하기 다익스트라 문제도 내 바로 전 상태를 기록하고 싶다면 방문했던곳인지 확인하는 배열에 바로 전 값을 넣어서 풀면 쉽게 풀린다.
• 역추적은 전체 걸린 횟수와 관련이 많은 것 같다.