글 읽기 - 정답은 맞췄는데 속도를 향상시키려면 어떻게하면 좋을까요???

cocobo123 6년 전 0

안녕하세요~~

c로 해서 인접행렬로 그래프 구현하고

dfs는 재귀, bfs는 큐로 구현해서 맞췄습니다.

그런데 4MS로 나와서 저두 0MS로 향상시키고 싶은데

다른 코드를 봐도 구현에 큰 차이가 없는 거같은데 어느 곳에서 속도를 향상시킬 수 있을까요???

아니면 단순히 c++ c의 차이일까요?? 궁금합니다.

#include<stdio.h>
int N, M, V;
int g[1001][1001];
int q[10000];
int fr, ed;
void BFS(int start)
{
	int pop;
	q[ed++] = start;
	g[start][start] = 1;
	while (fr != ed)
	{
		printf("%d ",pop = q[fr++]);
		for (int i = 1; i <= N; i++)
			if (g[pop][i] == 1 && g[i][i] != 1)
			{
				q[ed++] = i;
				g[i][i] = 1;
			}
	}
	printf("\n");
}

void DFS(int start)
{
	g[start][start] = 1;
	printf("%d ", start);
	for (int i = 1; i <= N; i++)
	{
		if (g[i][i] != 1)
		{
			if (g[start][i] == 1)
				DFS(i);
		}
	}
}
int main()
{
	scanf("%d %d %d", &N, &M, &V);
	for (int i = 0; i < M; i++)
	{
		int f, t;
		scanf("%d %d", &f, &t);
		g[f][t] = g[t][f] = 1;
	}
	DFS(V);
	printf("\n");
	for (int i = 1; i <= N; i++)
		g[i][i] = 0;
	BFS(V);
	return 0;

}

jjwdi0 6년 전 1

DFS, BFS를 인접행렬로 구현하면 시간복잡도가 O(V²)이지만, 인접리스트로 구현하면 O(V+E)가 됩니다. (V는 정점 개수, E는 간선 개수)

문제에서 간선 개수의 상한이 10000개 이므로 인접 리스트로 구현하면 더 빠를 것 같네요.

cocobo123 6년 전 0

감사함돠

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

문제

문제

출처

ICPC

정답은 맞췄는데 속도를 향상시키려면 어떻게하면 좋을까요???

cocobo123 6년 전 0

jjwdi0 6년 전 1

cocobo123 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말