백준 1197 : 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

MST 기본문제.

Unionfind

findRoot 할때 메모이제이션하는것 잊지말자.

현재 노드에서 재귀적으로 갈 수 잇는 최대 root를 바로 vRoot에 저장하면

속도를 훨씬 줄일 수 있다.

Kruskal은 항상 작은 비용이 드는 간선부터 확인해보되

간선이 연결하고 있는 두 노드 i 와 j 가 이미 연결되어있나 확인하고

연결이 안되어있을때 연결시켜준다.

연결여부 확인은 서로의 루트노드를 재귀적으로 따라가서 그 결과

루트노드가 같은지 여부를 확인하는 것이다.

연결해주는 것은 서로의 루트노드에 상하관계를 만들어주는 것이다.

j 의 최상단 루트의 루트를 i 의 최상단루트로 처리한다.

따라서 현재 i 와 j 를 포함한 모든 노드들의 최상단 루트는 i 의 최상단루트로 통일된다.

또한 처음에 속도가 100ms가 나왔는데 다른 분들은 c++ 기준 100ms 이하로 풀었길래

어디서 속도를 줄일 수 있을 지 고민해보았다.

일단 가장 확실한 방법은 무조건

ios_base::sync_with_stdio(false);

cin.tie(0);

을 쓰고 시작하는 것이다. 이 두 줄 추가했더니 36ms가 되었다.

단 이때는 cin, cout 과 printf, scanf 를 혼용해서 사용하면 안된다.(무조건 cin, cout만)

printf 와 scanf 를 사용 하는 것이 제일 무난하지만 cout 과 cin 에 익숙해서..

위에 두 줄 추가하면 printf, scanf와 비슷한 성능을 낼 수 있다.

https://algospot.com/forum/read/2496/

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; int v, e; class Edge{ public: int i = 0; int j = 0; int weight = 0; bool operator<(const Edge &v) const{ return weight < v.weight; } Edge(int i = 0, int j = 0, int weight = 0) :i(i), j(j), weight(weight) {} }; int vRoot[10001] = {0, }; vector<Edge> edges; int cost = 0; int findRoot(int v){ if(vRoot[v] == v){ return v; } return vRoot[v] = findRoot(vRoot[v]); } void kruskal(){ //sort부터 한다 weight 오름차순으로 //각 노드의 루트를 정의해준다 sort(edges.begin(), edges.end()); for(Edge it : edges){ //현재 간선을 놓을때 cycle이 발생하나 여부 확인 //-> 노드 i 와 노드 j 의 각 뿌리가 같으면 cycle 발생(이미 연결되어있다) //-> 각 뿌리가 다르면 연결해도 됨. int rootI = findRoot(it.i); int rootJ = findRoot(it.j); if(rootI != rootJ){ //union find 연결. //서로의 뿌리끼리 연결해준다. vRoot[rootJ] = rootI; cost += it.weight; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> v >> e; for(int i = 1; i <= v; i++){ vRoot[i] = i; } while(e--){ int i, j, w; cin >> i >> j >> w; edges.push_back(Edge(i, j, w)); } kruskal(); cout << cost << endl; return 0; }