글 읽기 - DFS 시간초과 이유를 여쭙고 싶습니다.

legendmic2 3년 전 0

DFS로는 계속 시간초과가 나서, BFS로 다시 풀고있습니다.

그러던 중에, 왜 시간초과가 나는지 궁금해서 질문드립니다.

질문게시판에서 알려주신 반례중 가장 대표적인 것이 {1, 0}이었는데요, 제 코드도 이때 오류가 납니다.

디버깅을 해보니, pos==4700일때 stack overflow라는 exception이 뜨더라구요.

컴파일러에 할당된 메모리보다 더 많은 연산처리를 필요로해서 멈춰버리는건가요?

끝까지 읽어주셔서 감사합니다.

#include <iostream>

#define MAX 100000

using namespace std;
 
bool visited[MAX + 1]; // 방문 기록 배열
int N, K;
// N : 수빈이 위치,  <= 10만
// K : 동생 위치 <= 10만
int minTime = MAX; // 0부터 10만까지 1칸씩 이동할때의 시간을 초기값으로

// 현재 pos의 위치, time만큼의 시간이 소모됨
void DFS(int pos, int time)
{
	if (pos == K && time < minTime)
	{
		minTime = time;
		return;
	}
	if (time + 1 < minTime) // 현재 소모된 시간보다 1초 더 갔을 때, 가장 빠른 시간보다 작다면
	// = 1초 더 이동할 가치가 있는 상황이라면
	{
		// pos+1이 유효한 위치라면 DFS
		if (pos+1 >= 0 && pos+1 <= MAX)
		{
			visited[pos + 1] = true;
			DFS(pos + 1, time + 1);
			
		}
		//pos-1이 유효한 위치라면 DFS
		if (pos-1 >= 0 && pos-1 <= MAX)
		{
			visited[pos - 1] = true;
			DFS(pos - 1, time + 1);
			
		}
		// pos*2이 유효한 위치라면 DFS
		if (pos<<1 >= 0 && pos<<1 <= MAX)
		{
			visited[pos << 1] = true;
			DFS(pos << 1, time + 1);
			
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	 cin >> N >> K;

	 visited[N] = true;
	 DFS(N, 0);
	
	 cout << minTime << endl;

}