글 읽기 - 오일러 회로 시간초과.. map의 문제일까요 재귀의 문제일까요

medic_programmer 6년 전 0

이 문제 해법을 고민한 끝에 오일러 회로를 구해야 한다는 결론에 이르렀습니다.

그래서 DFS를 이용해 오일러 회로를 구하는 코드를 작성했는데, 20%정도에서 시간초과가 발생합니다.

제가 예상하는 원인은 두가지로, 재귀호출 과정에서 stack overflow와 map의 성능 문제입니다.

(map은 이미 방문한 두 간선을 저장하는 과정에서 이용했습니다 - map을 이용하지 않고 짤 수 있는 기법이 있다면 알려주시면 감사하겠습니다!)

그런데 V와 E 모두 10만 이하라.. 깊이가 많아야 10만번 호출인데 stack overflow가 걸릴 수 있나요?

map이 아무리 느린 O(lgN) 이라지만 역시 제한이 10만인데 ㅠㅠ

뭐가 문제일까요! 알고리즘상의 문제일까요??

#include<stdio.h>
#include<map>
#include<vector>
#include<utility>
#define MIN(A,B) ((A)>(B)?(B):(A))
#define MAX(A,B) ((A)<(B)?(B):(A))
#define M 400002

using namespace std;

int N,E,EP,Euler[M],visited[M],degree[M],a[M],b[M],cnt;
vector<int> d[M];
map<pair<int,int>, int> chk,ans;

bool f(int a,int b)
{
	return chk.count(make_pair(MIN(a,b),MAX(a,b)));
}

void g(int a,int b)
{
	chk[make_pair(MIN(a,b),MAX(a,b))] = 1;
}

void DFS(int here)
{
	int i;
	
	visited[here] = 1;
	
	for(i=0; i<d[here].size(); i++){
		
		if(f(here,d[here][i]) == 0){
			g(here,d[here][i]);
			DFS(d[here][i]);
		}
	}
	
	Euler[++EP] = here;
	
}

void Get_Ans(int s)
{
	int j,A,B,alt=1;
	
	for(j=1; j<=EP; j++){
		
		A = Euler[(j+s-2)%EP+1]; B = Euler[(j+s-1)%EP+1];
		ans[make_pair(MIN(A,B),MAX(A,B))]= alt;
		alt = 3 - alt;
	}
}

int main()
{
	int i,Two,NPO,j;
	
	scanf("%d%d",&N,&E);
	
	for(i=1; i<=E; i++){
		
		scanf("%d%d",&a[i],&b[i]);
		
		degree[a[i]]++; degree[b[i]]++;
		d[a[i]].push_back(b[i]);
		d[b[i]].push_back(a[i]);
		
	}
	
	for(i=1; i<=N; i++){
		
		if(degree[i] % 2 == 1){
			degree[i] ++;
			degree[N+1] ++;
			d[N+1].push_back(i);
			d[i].push_back(N+1);
		}
	}
	
	for(i=1; i<=N; i++){
		
		chk.clear();
		
		if(!visited[i]){
			
			EP = 0;
			DFS(i);
			EP--;
			
			Two = NPO = 0;
			
			for(j=1; j<=EP; j++){
				
				if(degree[Euler[j]] != 2) Two = j;
				if(Euler[j] == N+1) NPO = j;
					
			}
			
			if(Two == 0 && EP % 2 == 1 && NPO == 0){
				printf("0\n");
				return 0;
			}
			
			else{
				if(NPO != 0) Get_Ans(NPO);
				else if(Two != 0) Get_Ans(Two);
				else Get_Ans(1);
			}
		}
	}
	
	for(i=1; i<=E; i++){
		printf("%d\n",ans[make_pair(MIN(a[i],b[i]),MAX(a[i],b[i]))]);
	}
	
	return 0;
}	

yukariko 6년 전 0

제 생각에 코드의 시간복잡도가 문제가 아니라면

map이 문제일 것 같습니다.

코드를 자세하게 보진않앗지만

a->b로 가는 간선마다 index를 붙여서 관리하면

map이아닌 bool형 배열로 체크가 가능하지 않을 까 생각됩니다.

medic_programmer 6년 전 0

@yukariko

ㅠㅠ 하지만 맵을 쓰지 않아도 TLE는 개선되는 것 같지 않습니다.. ㅠㅠ

혹시 코드 한번만 더 봐주실 수 있나요? 아무리 생각해도 stack overflow는 문제가 아닐 것 같아서요 ㅠ

yukariko 6년 전 0

코드의 시간복잡도가 O(VE)가 아닌가요?

check 배열을 매번 초기화하고 탐색을 하다보니 시간초과가 날것같습니다.

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

문제

문제

출처

ICPC

오일러 회로 시간초과.. map의 문제일까요 재귀의 문제일까요

medic_programmer 6년 전 0

yukariko 6년 전 0

medic_programmer 6년 전 0

yukariko 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말