글 읽기 - 게시판에 있는 반례들은 만족하는데.. 코린이 도와주실분 ㅜ

minripex 3년 전 0

시간초과문제가 나는데 DFS를 돌때 시간초과가 생기는건지요?,,,

사이클을 만족시키는 그래프/자기자신을 가리키는상황/서로를 가리키는 상황/사이클이 몇명을 빼고 만족시키는경우

이렇게 case별로 코드를 짯는데 시간초과를 어떻게 해결해야할지 감이안잡히네요 ..

DFS재귀 과정에서 문제있는건지 흠...

#include<bits/stdc++.h>
using namespace std;
#define MAX	100001

int Testcase,n;
int arr[MAX];
bool visited[MAX];	//들렀던 수인지 확인 
bool visited2[MAX];  //사이클이 앞에 몇개 두고 끊기는경우 
int cntvisited[MAX];//끊겼을때 몇명이 한팀을 이룰수있는지 체크하기위해 
int firstnum;
int nextn;
int cnt;
int sum=0;

vector<int> sumv;

void init()
{
	cnt=0;
}

int DFS(int x)
{
	if(visited2[x])
	{
		return cnt-cntvisited[x]+1;
	}
	if(visited[x])
	{
		return 0;
	}
	
	visited[x]=true;
	visited2[x]=true;
	cnt++;
	cntvisited[x]=cnt;
	nextn=arr[x];
	
	if(nextn==firstnum)
	{
		return cnt;
	}
	else if(nextn==x)
	{
		return 1;
	}
	else if(nextn!=firstnum)
	{
		return DFS(nextn);
	}
	
	
}


int main()
{
	cin>>Testcase;
	while(Testcase--)
	{
		sum=0;
		
		cin>>n;
		
		for(int i=1;i<=n;++i)
		{
			cin>>arr[i];
		}
		for(int i=1;i<=n;++i)
		{
			if(visited[i])
			{
				continue;
			}
			firstnum=i;
			init();
			sum+=DFS(i);
			memset(visited2,0,sizeof(visited2));
		}
		
		sumv.push_back(n-sum);
		memset(arr,0,sizeof(arr));
		memset(visited,0,sizeof(visited));
	}
	
	for(int i=0;i<sumv.size();++i)
	{
		cout<<sumv[i]<<'\n';
	}
	return 0;
}

fin 3년 전 0

78번 줄에 memset함수로 크기가 100001인 배열을 n번 초기화 해주는데 여기서 TLE 나는 걸로 생각됩니다.

n이 최대 100,000이므로 memset의 시간복잡도가 단순히 O(N)이라 가정하더라도 O(N^2)의 시간복잡도를 가지는 것으로 보입니다.

memset의 시간복잡도는 자세히 알 수 없지만 for문으로 초기화 하는 것보다 대체로 빠를 뿐이지 시간복잡도가 O(1)은 아닌 것으로 알고 있습니다,

O(N^2)일 경우 N은 최대 100000이므로 100억번 실행되므로 memset이 for문보다 10배 빠르더라도 10억번 실행되므로 TLE나지않을까,, 예상해봅니다.

한번 초기화 방법을 바꿔보는건 어떨까요?

코딩고수는 아니지만 답변이 없어서 달고갑니다 :)

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

문제

문제

출처

ICPC

게시판에 있는 반례들은 만족하는데.. 코린이 도와주실분 ㅜ

minripex 3년 전 0

fin 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말