3-G_12851 숨바꼭질2

작성한 질문수 25

0

안녕하세요 효민님 ㅎㅎ

이 문제는 재귀로 풀면 안됩니다.

	}
	if (a>b){
		go(a-1, b, cnt+1);
		visited[a-1]=0;
	}
	else {
		if(a+1 <= 100000 && visited[a+1]==0){
			go(a+1, b, cnt+1);
			visited[a+1]=0;
		}
		if(a*2 <= 100000 && visited[a*2]==0){
			go(a*2, b, cnt+1);
			visited[a*2]=0;
		}
	}

이렇게 하시면 go(a - 1, b) .. 이게 깊숙히 먼저 재귀적으로 탐색되게 되고...

결국

시간초과가 나게 됩니다.

문제 자체가 가중치가 같은 그래프에서 최단거리를 탐색 = BFS라고 보시면 됩니다.

재귀로 풀게 되면 깊이 있게 탐색을 하게 되죠?

즉, 최단거리로도 찾을 수 있는데 재귀로 풀게 되어서 빨리 갈길을 돌아서 가게 되는 것입니다.

그림으로 그리면 이렇게 되는 것이죠. BFS는 2번만에 정답을 찾을 수도 있는데 DFS는.. 멀리 가버렸습니다.. ㅠㅠ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.