글 읽기 - 시간초과가 나오는데 어떻게 개선할 수 있을까요?

idjjm95 2년 전 0

제딴에는 크루스칼 알고리즘을 이용하기 위해서

priority queue를 이용해서 간선들의 가중치를 오름차순으로 정렬한다음에

어떤 노드 값이 0 이면 아직 간선으로 연결되지 않은 노드라 생각해서

값을 1을 주고

지나온 edge(변수 cnt)를 증가시키는 방향으로 코딩했습니다.

혹시 어디에서 시간이 낭비되고 있는걸까요?

#define _CRT_SECURE_NO_WARNINGS

#include<functional>
#include<iostream>
#include<algorithm>
#include<queue>
#include<tuple>
#include<string.h>
using namespace std;

class comp {
public:
	bool operator()(const tuple<int, int, int>& LHS, const tuple<int, int, int>& RHS)
	{
		return get<2>(LHS) > get<2>(RHS);
	}
};

int V, E;
priority_queue < tuple<int, int, int >, vector<tuple<int, int, int>>, comp> PQ; //노드. 노드, 간선
int fst, sec, thr; // 노드 노드 간선
int visited[10001];
int cnt = 0;// 현재까지의 edge
int result = 0;
tuple <int, int, int> temp;

int main()
{
	scanf("%d %d", &V, &E);
	memset(visited, 0, sizeof(visited));
	
	for (int i = 0; i < E; i++)
	{
		scanf("%d %d %d", &fst, &sec, &thr);
		PQ.push(make_tuple(fst, sec, thr));
	}
	

	while (cnt+1 != V)
	{
		temp = PQ.top();
		PQ.pop();
		if((visited[get<0>(temp)]==0) || (visited[get<1>(temp)]==0))
		{
			cnt++;
			visited[get<0>(temp)] = 1; visited[get<1>(temp)] = 1;
			result += get<2>(temp);
		}
	}
	
	printf("%d", result);
	
	return 0;
}

kdh6429 2년 전 1

이 코드로는 정상적인 결과를 얻을 수 없습니다.

예를 들어 1-2 를 연결하고 3-4를 연결하면 2-3을 연결하지 않게 됩니다.

0000000000 2년 전 1

참고로 크루스칼 알고리즘은 Union_Find를 사용해야 효율적인 구현이 가능하니 Union_Find를 먼저 공부해 보시거나 프림 알고리즘을 사용하시는 게 나을 것 같습니다.

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

문제

문제

출처

ICPC

시간초과가 나오는데 어떻게 개선할 수 있을까요?

idjjm95 2년 전 0

kdh6429 2년 전 1

0000000000 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말