글 읽기 - 9370번 다익스타 알고리즘 시간초과가 뜹니다.

yangmin0513 4년 전 0

다익스트라를 3번써서 풀었습니다. 문제는 테스트 케이스를 한번씩 할때마다 weight라는 2차원배열을 초기화 하는 create_graph함수를 호출합니다.

create_graph의 시간복잡도가 O(n^2)인데 이거를 테스트 케이스가 돌때마다해서 O(n^3)을 으로 시간복잡도가 되서 시간초과가 뜨는걸까요??

아니면 마지막에 출력을 맞출려고 정렬시 퀵소트O(n*logn)을 사용하는것이 문제일까요.

출력은 에제 출력과 동일하게 터미널상에서 나오는데 시간복잡도를 줄이지를 못하겠습니다.

#include <stdio.h>

#define TRUE 1
#define FALSE 0
#define NV  2001// number of vertices
#define INF 10000 // infinite (not connected)


int weight[NV][NV];
int distance[NV];
int found[NV];

int dijkstra(int v, int n,int destination);
int choose(int distance[], int n, int found[]);
void quicksort(int low, int high,int *S);
void partition2(int low,int high, int *pivotpoint,int *S);


void create_graph(int n)
{
	int i,j;

	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i==j)
				weight[i][j]=0;
			else
				weight[i][j]=INF;
		}
	}
}
int choose(int distance[], int n, int found[])
{//find the smalles distance not yet checked
	int i,min,min_pos;
	min=INF;
	min_pos=-1;

	for(i=1;i<n;i++)
	{
		if(found[i]==0 && distance[i]<min)// 왜 found[3]==0??? 
		{
			min=distance[i];
			min_pos=i;
		}
	}
	return min_pos;
}

int dijkstra(int v, int n,int destination)
{
	 /* v is the starting point.
	n is the number of vertices.
	distance[i] repint v, int n,int destination, int resultresents the shortest path from vertex v to i.
	found[i] is 0 if the shortest path from i has not been found, and 1 if it has.
	cost is the adjacency matrix.
	*/

	int i,u,w;

	for(i=0;i<=n;i++)
	{
		found[i]=FALSE;
		distance[i]=weight[v][i];
	}

	found[v]=TRUE; // 일단 1부터 시작이라 찾았다고 설정 
	distance[v]=0; 

	for(i=1;i<n-2;i++)
	{
		u=choose(distance,n,found);
		if(u<0)
			continue;
		found[u]=TRUE;

		for(w=1;w<=n;w++)
		{
			if(found[w]==0)
			{
				if(distance[u]+weight[u][w] <distance[w])
				{
					distance[w]=distance[u]+weight[u][w];//distance[1]=7;
				}
			}
		}

	}
	return distance[destination];
}
void input()
{
	int i,j,k=0;;
	int n,m,t; // 2<=n<=2000,  1<=m<=50000   1<t<=100
	int s,g,h;
	int a,b,d;
	int T;//테스트 횟수 // 1<T<=100
	int final_dest[101];//목적지 후보들 개수 1<t<=100
	
	int result1,result2,result3;
	int main_dist;
	int pass;
	int solution[101];

	create_graph(NV);
	scanf("%d",&T);

	for(i=0;i<T;i++)
	{
		scanf("%d%d%d",&n,&m,&t);// 노드,엣지,목적지 후보개수 입력 
		scanf("%d%d%d",&s,&g,&h); // 시작정점, 거쳐가야하는 간선  입력 
		
		create_graph(n+1);// n^2의 시간복잡도 

		for(j=0;j<m;j++)
		{	
			scanf("%d%d%d",&a,&b,&d);
			weight[a][b]=weight[b][a]=d; //그래프 생성 
		}
		for(j=0;j<t;j++)
		{
			scanf("%d",&final_dest[j]);//목적지 후보들 입력 
		}
		

		if(weight[s][g]!=INF&&weight[s][h]==INF)// 노드 s랑 g가 연결되있으면 
		{
			result1=dijkstra(s,n,g);// 
			result2=dijkstra(g,n,h);// 
			pass=0;
			
		}
		else if(weight[s][g]==INF&&weight[s][h]!=INF)
		{
			result1=dijkstra(s,n,h);//2->1
			result2=dijkstra(h,n,g);//1->3
			pass=1;
		}

		for(j=0;j<t;j++)
		{
			main_dist=dijkstra(s,n,final_dest[j]);
			
			if(pass==1)
				result3=dijkstra(g,n,final_dest[j]);	
			else if(pass==0)
				result3=dijkstra(h,n,final_dest[j]);

			if(result1+result2+result3<=main_dist)
			{
				//solution[k++]=final_dest[j];
				// if(i==1){
				// 	printf("%d ",final_dest[j]);
				// }	
				//printf("%d ",final_dest[j]);
				solution[k++]=final_dest[j];
			}
		}		
		quicksort(0,--k,solution);	
		for(int l=0;l<=k;l++)
		{
			printf("%d ",solution[l]);
		}
		k=0;
	}
}

void quicksort(int low, int high,int *S)
{
	int pivotpoint;

	if(high>low)// 분할을 리스트의 크기가 0이나 1이 될떄까지 반복 
	{
		partition2(low,high,&pivotpoint,S);
		quicksort(low,pivotpoint-1,S);
		quicksort(pivotpoint+1,high,S);
	}

}

void partition2(int low,int high, int *pivotpoint,int *S)
{
	int lower,upper;
	int pivotitem;
	int temp;

	pivotitem=S[low]; // pivotitem으로 첫 원소 선택 

	lower=low+1;
	upper=high;

	while(lower<upper)
	{
		while(lower<upper && S[lower]<=pivotitem) // 5 3 8 4 9 1 6 2 7
			lower++;                                //        lower=2 >>8  lower=4 >>9
		while(lower<upper && S[upper]>=pivotitem)
			upper--;                                //  upper= 7 >> 2    upper=5 >> 1 

		if(lower<upper) // S[lower]와 S[upper] 교환 
		{                          /// 5 3 2 4 9 1 6 8 7 
			temp=S[lower];          /// 5 3 2 4 1 9 6 8 7
 			S[lower]=S[upper];
			S[upper]=temp;
		}

	}
// lower =5 
	if(S[lower]>pivotitem)  //9>5
		*pivotpoint=lower-1; //4   >> 1   S[pivotpoint]==1
	else
		*pivotpoint=lower;

	temp=S[low];
	S[low]=S[*pivotpoint];
	S[*pivotpoint]=temp;

}
int main()
{
	int i;
	input();		

	return 0;
}

pikkoro97 4년 전 0

이차원 배열로 다익스트라를 돌리면 시간 복잡도가 T(|V|^2 + logE)가 나옵니다. 모든 노드가 한번씩은 큐에서 뽑히는데 한 노드 당 V만큼 if문을 돌려야 하기 때문에 V^2이 걸리고 큐에 최대 E(실제 엣지 개수) 만큼 들어가기 때문입니다. 이차원 배열은 플로이드 쓰거나 E가 V^2에 근접하는 거 아니면 쓰지 않는 걸 추천드립니다.

pikkoro97 4년 전 0

위에 시간복잡도 logE가 아니라 ElogE입니다.

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

문제

문제

출처

ICPC

9370번 다익스타 알고리즘 시간초과가 뜹니다.

yangmin0513 4년 전 0

pikkoro97 4년 전 0

pikkoro97 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말