글 읽기 - 시작하자마자 틀리다고 나오네요

whobc 6년 전 0

크루스칼 알고리즘으로 최소 스패닝 트리를 구성했습니다.

로컬에서 제가 만든 테스트 케이스는 모두 통과하는데

제출하니 시작하자마자 틀리다고 나오네요.

어느 입력에서 틀린 건지 찾기가 매우 힘드네요.

구현한 크루스칼 알고리즘에 대해서 간단히 설명드리면

1. 먼저 입력받은 v1, v2, w 중에서 v1과 v2의 성별이 다를 때만 Min Heap에 집어 넣습니다.

2. 그 후 Min Heap에서 하나씩 Pop해서 싸이클 테스트를 해서 싸이클이 안 만들어지면 정답에 추가합니다.

3. 2의 과정을 N-1 개의 간선을 찾을 때까지 반복합니다.

이렇습니다. 어디가 문제인지 도와주세요!

----------------------------------------추가 질문----------------------------------------

Union-Find 함수를 보편적인 방식으로 수정하니 정답이네요.

하지만 아래 구현되어 있는 Union-Find 를 사용했을 때 오답이 되는 예외를 아직 발견하지 못했습니다.

아래의 Union-Find 함수는 어느 부분이 잘못된 걸까요?

#include <stdio.h>

#define MAX_VTX 1000
#define MAX_EDGE 10000

int N, M;
char gender[MAX_VTX + 1];

typedef struct HeapNode {
	int v1;
	int v2;
	int w;
} HeapNode;

HeapNode H[MAX_EDGE + 1];
int Hi;

void InsertHeap(int v1, int v2, int w)
{
	HeapNode node = { v1, v2, w };
	int parent, child;

	child = ++Hi, parent = child / 2;
	while (parent > 0)
	{
		if (node.w >= H[parent].w)
			break;

		H[child] = H[parent];
		child = parent, parent = child / 2;
	}

	H[child] = node;
}

HeapNode DeleteHeap()
{
	HeapNode retNode = H[1];
	HeapNode node = H[Hi--];
	int parent, child;

	parent = 1, child = 2;
	while (child <= Hi)
	{
		if (child < Hi && H[child].w > H[child + 1].w)
			child++;

		if (node.w <= H[child].w)
			break;

		H[parent] = H[child];
		parent = child, child = parent * 2;
	}

	H[parent] = node;
	return retNode;
}

int R[MAX_VTX + 1];

int Find(int v)
{
	return R[v];
}

void Union(int v1, int v2)
{
	int i;

	if (R[v1] < R[v2])
	{
		for (i = 1; i <= N; i++)
		{
			if (R[i] == R[v2])
				R[i] = R[v1];
		}
	}
	else
	{
		for (i = 1; i <= N; i++)
		{
			if (R[i] == R[v1])
				R[i] = R[v2];
		}
	}
}

int Kruskal()
{
	int i, count, ans = 0;
	HeapNode hNode;

	for (i = 1; i <= N; i++)
		R[i] = i;

	for (count = 0; Hi && count < N - 1; )
	{
		hNode = DeleteHeap();

		if (Find(hNode.v1) != Find(hNode.v2))
		{
			count++;
			ans += hNode.w;
			Union(hNode.v1, hNode.v2);
		}
	}

	if (count < N - 1)
		ans = -1;

	return ans;
}

int main(void)
{
	int i, v1, v2, w;
	char g;

	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++)
	{
		getchar();
		scanf("%c", &g);
		gender[i] = g;
	}

	Hi = 0;
	for (i = 0; i < M; i++)
	{
		scanf("%d %d %d", &v1, &v2, &w);
		if (gender[v1] != gender[v2])
			InsertHeap(v1, v2, w);
	}

	printf("%d\n", Kruskal());

	return 0;
}

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