글 읽기 - C 시간초과 무신일이고,,, dfs재귀

gue707 3년 전 0

dfs 재귀써서 풀었는데 8%에서 시간초과로 멈추네요 ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int N,check[2000] = { 0 };
typedef struct person
{
	int f;
	int fn[2000];
}per;

void init(per* x, int N)
{
	x->f = 0;

}

int dfs(per** num, int k ,int cnt)
{
	check[k] = 1;
	if (cnt == 4) return cnt;
	for (int i = 0; i < N; i++)
	{
 		if (num[k]->fn[i] == 1 && check[i] != 1)
		{

			if (dfs(num, i, cnt + 1) == 4) { return 4; }
		}
	}
	check[k] = 0;
	return 0;
}

int main() {
	int M,k=0;
	scanf("%d %d", &N, &M);
	per* num[2000];
	for (int i = 0; i < N; i++)
	{
		num[i] = malloc(sizeof(per));
		init(num[i], N);
	}
	for (int i = 0; i < M; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		(num[x]->fn)[y] = 1; (num[x]->f)++;
		(num[y]->fn)[x] = 1; (num[y]->f)++;
	}
	for (int i = 0; i < N; i++)
	{

		if (dfs(num, i, 0) == 4) { k=1; break; }
	}
	printf("%d", k);

	return 0;
}

leinad2 3년 전 0

코드의 시간복잡도에 대해서 알아보시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

C 시간초과 무신일이고,,, dfs재귀

gue707 3년 전 0

leinad2 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말