글 읽기 - 접근 방법 좀 알려주세요 ㅠㅠ

yeop9657 8년 전 0

혼자서 공부 하려니깐 너무 어렵습니다...

이문제는 어떤 방식으로 접근을 해서 풀어야 하는건가요?

찾아서 해보았는데;;; 왜 34가나올까요;;;

물어볼사람도 없고 미치것습니다.

#include <iostream>
#include <algorithm>
#define SIZE 100001
using namespace std;

typedef struct edge * EPtr;
typedef struct edge
{
	int N; /* 시작점 */
	int M; /* 도착점 */
	int W; /* 가중치 */
}Edge;

Edge mEdge[SIZE];
int t[SIZE];

/* Quick Sort 비교 함수 */
int compare(const void * e1, const void * e2)
{
	/* Edge */
	EPtr temp1 = (EPtr)e1, temp2 = (EPtr)e2;
	/* 가중치를 비교를 하여 참과 거짓으로 구분 */
	return (temp1->W > temp2->W) ? 1 : 0;
}

/*  */
int kruskal(int N, int M)
{
	/* 가중치의 합을 저장하는 변수 */
	int Sum = 0;

	/* */
	for (int ii = 1; ii <= N; ii++) { t[ii] = ii; }
	/* */
	for (int jj = 0; jj < M; jj++)
	{
		if (t[mEdge[jj].N] != t[mEdge[jj].M])
		{
			if (t[mEdge[jj].N] < t[mEdge[jj].M]) { t[mEdge[jj].M] = t[mEdge[jj].N]; }
			else { t[mEdge[jj].N] = t[mEdge[jj].M]; }

			/* */
			Sum += mEdge[jj].W;
		}
	}
	return Sum;
}

int main(void)
{
	/* 정점, 간선 입력 */
	int N = 0, M = 0;
	cin >> N >> M;

	/* 정점, 간선, 가중치 정보 입력 */
	for (int count = 0; count < M; count++) { cin >> mEdge[count].N >> mEdge[count].M >> mEdge[count].W; }
	/* Quick Sort */
	qsort((void *)mEdge, M, sizeof(mEdge[0]), compare);

	/**/
	cout << kruskal(N, M) << endl;

	return 0;
}

kesakiyo 8년 전 0

이 문제를 풀려면 그래프 자료구조를 알고 있어야 합니다.

Minimum Spanning Tree를 구하는 문제인데 이걸 효율적로 구할 수 있는 알고리즘은

대표적으로 prim algorithm, kruskal algorithm등이 있습니다

위 두 알고리즘은 비교적 많이 알고있는 알고리즘이기 때문에 구글링을 하시면 한글자료를 많이 얻으실 수 있을겁니다.

화이팅하세요~!!

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

문제

문제

출처

ICPC

접근 방법 좀 알려주세요 ㅠㅠ

yeop9657 8년 전 0

kesakiyo 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말