[TIL] 22-01-10

0

TIL

목록 보기
71/104
post-thumbnail

알고리즘 스터디

  • 종만북) 31장 최소 스패닝 트리 ~
  • 백준 1197 최소 스패닝 트리 O
  • 백준 1922 네트워크 연결 O
  • 백준 1647 도시 분할 계획 O
  • 백준 4386 별자리 만들기 O
  • 백준 1414 불우이웃 돕기 O
  • 백준 10423 전기가 부족해 O
  • 백준 23743 방탈출 O
  • 백준 1368 물대기 O

알고리즘 스터디

📌참고자료

크루스칼의 최소 스패닝 트리 알고리즘 구현

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

const int MAX_V = 100;

//크루스칼 최소 스패닝 트리 알고리즘
//트리를 이용해 상호 배타적 집합을 구현한다

struct DisjointSet {
	vector<int> parent, rank;
	DisjointSet(int n) : parent(n), rank(n, 1) {
		for (int i = 0; i < n; ++i)
			parent[i] = i;
	}

	//u가 속한 트리의 루트 번호 반환
	int find(int u) {
		if (u == parent[u]) return u;
		return parent[u] = find(parent[u]);
	}

	//u가 속한 트리와 v가 속한 트리를 합친다
	void merge(int u, int v) {
		u = find(u); v = find(v);

		//u와 v가 이미 같은 트리에 속하는 경우 걸러냄
		if (u == v) return;

		if (rank[u] > rank[v]) swap(u, v);
		parent[u] = v;
		if (rank[u] == rank[v]) ++rank[v];
	}
};

//정점의 개수
int V;
//그래프의 인접 리스트 (연결된 정점 번호, 간선 가중치) 쌍 저장
vector<pair<int, int>> adj[MAX_V];

//주어진 그래프에 대해 최소 스패닝 트리에 포함된 간선의 목록을 selected에 저장하고, 가중치의 합을 반환한다.
int kruskal(vector<pair<int, int>>& selected) {
	int ret = 0;
	selected.clear();

	//<가중치, <u, v>>의 목록을 얻는다
	vector<pair<int, pair<int, int>>> edges;
	for (int u = 0; u < V; ++u) {
		for (int i = 0; i < adj[u].size(); ++i) {
			int v = adj[u][i].first;
			int cost = adj[u][i].second;
			edges.push_back({ cost, {u, v} });
		}
	}
	//가중치순으로 정렬
	sort(edges.begin(), edges.end());

	//처음엔 모든 정점이 서로 분리되어 있다.
	DisjointSet sets(V);
	for (int i = 0; i < edges.size(); ++i) {
		int cost = edges[i].first;
		int u = edges[i].second.first;
		int v = edges[i].second.second;

		//간선 (u, v)를 검사한다.
		//이미 u와 v가 연결되어있을 경우(사이클) 무시
		if (sets.find(u) == sets.find(v)) continue;

		sets.merge(u, v);
		selected.push_back({ u, v });
		ret += cost;
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	return 0;
}

백준 1197 최소 스패닝 트리

백준 1647 도시 분할 계획

백준 4386 별자리 만들기

백준 1414 불우이웃 돕기

백준 10423 전기가 부족해

백준 23743 방탈출

백준 1368 물대기

profile
Be able to be vulnerable, in search of truth

0개의 댓글