글 읽기 - c언어 시간초과 오류

guftkcldh 3년 전 0

시간초과 오류가 뜨는데 어디서 뜨는지 잘 모르겠습니다. 고수님들 조언 부탁드립니다.

#include<stdio.h>

int field[1001][1001]={0};
int check[1001]={0};
int num, line;
int countd=0;
int countb=1;

void dfs(int point)
{
	printf("%d ",point);
	countd++;
	
	int i;
	
	for(i=0;i<num;i++)
	{
		if(countd==num) return;
		if(field[point][i+1]==1 && check[i+1]==0)
		{
			check[i+1]=1;
			dfs(i+1);
		}
	}
}

void bfs(int point)
{
	int i;
	
	int used[1001];
	
	for(i=0;i<num;i++)
	{
		if(countb==num) return;
		if(field[point][i+1]==1 && check[i+1]==0)
		{
			check[i+1]=1;
			printf("%d ",i+1);
			used[i+1]=1;
			countb++;
		}
	}
	
	for(i=0;i<1001;i++)
	{
		if(used[i]==1) bfs(i);
	}
}

int main()
{
	int start;
	int i;
	int a,b;
	
	scanf("%d%d%d",&num,&line,&start);
	
	for(i=0;i<line;i++)
	{
		scanf("%d%d",&a,&b);
		field[a][b]=1;
		field[b][a]=1;
	}
	
	check[start]=1;
	dfs(start);
	printf("\n");
	
	for(i=0;i<1001;i++)
	{
		check[i]=0;
	}
	
	check[start]=1;
	printf("%d ",start);
	bfs(start);
	
	return 0;
}

keykat 3년 전 1

BFS는 구현 방식이야 여러가지 있겠지만 보통 자료구조 queue로 구현합니다. 위 코드는 BFS 구현을 재귀적으로 했는데, 저렇게 하면 첫번째는 너비를 탐색한 후, 재귀 부분에서 깊이 우선 탐색과 같은 형태로 넘어갈 것 같습니다.

BFS는 queue에 있는 특정 노드를 꺼내어 탐색하고, 그 노드의 자식 노드 중에 방문한 적이 없는 노드를 queue에 넣는 과정을 queue가 빌 때 까지 반복합니다. (설명을 잘 못해 죄송합니다. 구글에서 찾아보면 좋은 설명이 엄청 많으니 한번 확인해 보세요 )

BFS 탐색만 따로 고쳐서 제출하니 정답처리가 되는걸 보아 DFS 문제는 아닌것 같습니다.

guftkcldh 3년 전 0

좋은 댓글 감사드립니다.

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

문제

문제

출처

ICPC

c언어 시간초과 오류

guftkcldh 3년 전 0

keykat 3년 전 1

guftkcldh 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말