[백준][C++] 20010 악덩 영주 혜유

20010. 악덩 영주 혜유

20010번: 악덕 영주 혜유

코드

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

 

 

알고리즘 설계

크게 두 가지를 구했다.

 

최소 스패닝 트리는 크루스칼 알고리즘을 이용해서, 두 마을 사이를 이동하는 가장 큰 비용은 DFS 알고리즘으로 구할 수 있었다.

 

 

1. 최소 스패닝 트리 구하기

• 간선을 비용에 대한 오름차순으로 저장한다.
• 사이클이 생기지 않도록 union-find 알고리즘을 통해 순서대로 N-1개의 간선을 구성한다.

2. 가장 큰 비용 구하기

• 노드별로 연결되어있는 간선, 노드를 저장한다.
• 0부터 N까지의 노드를 연결 되어있는 노드로 DFS로 탐색해준다.
• 탐색을 하는 동안 지금까지 경로의 합을 구한다.
• 구한 합들 중 가장 큰 비용이 최대 비용이다.

 

[백준][C++] 1260 DFS와 BFS

[백준][C++] 1197 최소 스패닝 트리

 

DSF와 크루스칼 알고리즘의 자세한 설명은 이 글에 각각 있다!

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Edge
{
	int a, b, w;

	bool operator < (const Edge& e) const
	{
		return w < e.w;
	}
};
struct Node
{
	int to, w;
};

int parents[1000];
unsigned long long result = 0, worst = 0;

bool visited[1000];
vector<Node> nodes[1000];
vector<Edge> edges;

// union-find
int find(int v)
{
	vector<int> vec;

	while (v != parents[v])
	{
		vec.push_back(v);
		v = parents[v];
	}

	for (int i : vec)
		parents[i] = v;

	return v;
}

// 최대 비용 구하기
void DFS(int v, int weight)
{
	visited[v] = true;

	for (int i = 0; i < nodes[v].size(); i++)
	{
		if (!visited[nodes[v][i].to])
		{
			// 방문한 적 없다면, 비용을 더해서 다음 탐색 호출
			DFS(nodes[v][i].to, weight + nodes[v][i].w);
		}
	}

	// 최대 비용 계산
	worst = max(worst, (unsigned long long)weight);
}

int main()
{
	int vCnt, lCnt, a, b, w;

	cin >> vCnt >> lCnt;

	for (int i = 0; i <= vCnt; i++) parents[i] = i;
	for (int i = 0; i < lCnt; i++)
	{
		cin >> a >> b >> w;
		edges.push_back({ a,b,w });
	}

	// 크루스칼 알고리즘
	sort(edges.begin(), edges.end());

	for (int i = 0; i < edges.size(); i++)
	{
		Edge edge = edges[i];
		int fa = find(edge.a), fb = find(edge.b);

		if (fa != fb)
		{
			result += edge.w;
			parents[fa] = fb;

			// 각 노드에 연결된 정점, 간선을 저장
			nodes[edge.a].push_back({ edge.b, edge.w });
			nodes[edge.b].push_back({ edge.a, edge.w });
		}
	}

	// 0부터 N까지 경로를 계산
	for (int i = 0; i < vCnt; i++)
	{
		// 계속 visited 초기화
		for (int i = 0; i < vCnt; i++)
			visited[i] = false;

		DFS(i, 0);
	}

	cout << result << '\n' << worst;
}

 

최소 스패닝 트리를 구하는 건 정말 오랜만이라, 많이 헤맸다. 최대 비용을 구하는 아이디어도 바로 생각나지 않고, 시간이 많이 걸렸던 것 같다. 다음에 MST를 요구하는 문제가 나온다면, 5분만에 풀어주겠다.

 

그래도 크루스칼 알고리즘과 DFS로 원하는 결과를 구해내서 뿌듯했다!