글 읽기 - find 재귀함수 시간 초과 문제

bgg0223 4년 전 0

크루스칼 알고리즘으로 문제를 풀었는데요!

find함수에서

- 시간 초과 나는 경우

else{

return find(x);

}

이렇게 하면 시간초과 나고

- 시간 초과 나지 않는 경우

else{

return top[x] = find(x);

}

이렇게 하면 시간초과 나지않고 해결됩니다.

둘이 무슨 차이인가요??

#include<stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
pair<int,pair<int,int>> route[1000005];
int top[100006];
int aa, bb, cc;
int n, m;


int find(int x) {
	if (top[x] == x) return x;
	else {
        /***************************이부분*******************************/
		return top[x] = find(top[x]);
	}
}
void unionn(int a, int b) {
	int ra = find(a), rb = find(b);
	top[ra] = rb;
}
int main(){
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) top[i] = i; //make_set;
	for (int i = 0; i < m; i++) {

		scanf("%d %d %d", &aa, &bb, &cc);
		route[i] = make_pair(cc, make_pair(aa, bb));
	}
	int ans=0;
	sort(route, route+m);
	//n-2개의 edge선택
	int e = n - 2;
	for (int i = 0; i < m; i++) {
		int a = route[i].second.first, b = route[i].second.second;
		
		if (find(a) != find(b)) {
			unionn(a, b);
			//cout << a << " "<<b<<endl;
			ans += route[i].first;
			e--;
		}
		if (!e) break;
	}
	cout << ans << endl;
	return 0;
}

sait2000 4년 전 0

두 번째 경우는 반환해야 하는 값을 계산한 다음 그 값을 따라 올라갔던 모든 자리에 기록하므로 다음번에 다시 계산을 할 때 시간이 덜 걸립니다. 이름도 있습니다. 경로 압축 최적화라고.

첫 번째 거는 다음과 같은 입력이 들어오면 O(n^2)라서 시간초과가 날 겁니다 아마.

2 1 1

3 2 1

4 3 1

5 4 1

...

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

문제

문제

출처

ICPC

find 재귀함수 시간 초과 문제

bgg0223 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말