글 읽기 - c++ 시간초과 오류입니다. ㅠ

leekang9070 5년 전 1

방문한 곳의 COUNT가 과거 보다 작을 경우만 DFS 를 실행하는 코드입니다.

ㅠㅠㅠ 어디서 시간초과가 나오네요 ㅠ

#include<iostream>
using namespace std;
int result = 9999999;
int start;
int dep; 
int arr[1000000];
void dfs(int count, int position)
{
	if (position > dep +1)
	{
		return;
	}
	if (position < 0)
	{
		return;
	}
	if (arr[position] > count)
	{
		arr[position] = count;
		dfs(arr[position] + 1, position * 2);
		dfs(arr[position] + 1, position - 1);
		dfs(arr[position] + 1, position + 1);
		
	}
	else
	{
		return;
	}

}
int main()
{

	cin >> start >> dep;
	if (start == dep)
	{
		cout << 0 << endl;
	}
	else if (start > dep)
	{
		cout << start-dep << endl;
	}
	else
	{
		for (int i = 0; i <= dep + 1; i++)
		{
			arr[i] = 99999;
		}
		dfs(0, start);
		cout << arr[dep] << endl;
	}
}

djm03178 5년 전 1

이미 어떤 정점을 방문해서 그 뒤로 갈 수 있는 정점들을 전부 탐색하고 돌아왔는데, 그 정점으로 가는 더 짧은 길을 방문해서 그 뒤의 정점들을 다시 전부 탐색하고 돌아와야 한다면 엄청나게 큰 손해가 아닐 수 없습니다. 그래서 최단 거리는 무조건 BFS (DFS가 아니라)로 해야 합니다.

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 시간초과 오류입니다. ㅠ

leekang9070 5년 전 1

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말