BOJ 16202) MST 게임 & Kruskal Algorithm
먼저 MST는 Minimum spanning tree의 줄임말로, spanning tree는 다음과 같은 조건을 만족하는 간선의 집합이다.
- 스패닝 트리를 구성하는 간선의 개수는 N-1개이다.
- 그래프의 임의의 두 정점을 골랐을 때, 스패닝 트리에 속하는 간선만 이용해서 두 정점을 연결하는 경로를 구성할 수 있어야 한다.
이 스패닝 트리 중에서 간선의 가중치 합이 최소인 것을 MST라고 한다.
알고리즘은 상당히 간단한데, 다음과 같다.
1) edge들을 가중치로 정렬한다.
2) 가중치가 작은 것에서부터 큰 것들 순으로 각 edge가 MST를 만들 수 있는 지 없는지 확인한다.
(cycle을 만드는지 확인)
3) 만들 수 있으면 MST를 위한 집합에 집어넣는다.
예를 들어 다음과 같은 간선들을 보자. 가중치로 정렬되어 있다고 가정하자.
1. 2 4
2. 1 2
3. 4 6
4. 1 3
5. 2 3
6. 4 5
7. 5 6
MST = {}
먼저 1. 간선을 MST 집합에 넣는다고 cycle이 생기지 않으니 넣는다.
2. 1 2
3. 4 6
4. 1 3
5. 2 3
6. 4 5
7. 5 6
MST = { (2 4) }
(1 2) (4 6) (1 3) 도 마찬가지 이므로 넣는다.
MST = { (2 4) (1 2) (4 6) (1 3)}
근데 5. (2 3)을 넣을 경우 MST 집합의 (1 2) (1 3)에 의해 cycle을 형성한다. 그러므로 제낀다.
다음으로 6. (4 5)를 넣으면 MST 집합이 MST를 이루게 되므로 종료하게 된다.
그러면 이게 cycle을 만드는지 안 만드는지 어케 아느냐?
각 간선의 정점들을 통해 set을 만들면 쉽게 해결된다.
각 정점의 p(x) == p(y)면 cycle을 만드므로 그 상황에서는 넣지 않으면 된다.
이 점을 이용하면 16202) MST 게임을 쉽게 풀수 있다.
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 67 68 69 70 | #include <stdio.h> #include <utility> #include <algorithm> using namespace std; pair<int, int> edge[100001]; int N, M, K; int p[10001]; int size[10001]; int parent(int x){ if(p[x] == x) { return x; } return p[x] = parent(p[x]); } void addTree(int x, int y){ int px = parent(x); int py = parent(y); if(px == py) return; if(size[px] >= size[py]) { p[py] = px; size[px] += size[py]; } else { p[px] = py; size[py] += size[px]; } } int main() { scanf("%d%d%d", &N,&M,&K); for(int i=1; i<=M; i++) { scanf("%d%d", &edge[i].first, &edge[i].second); } for(int j=0; j<K; j++) { for(int i=0; i<=M; i++) { p[i] = i; size[i] = 1; } int cost = 0; int edgeCnt = 0; for(int i=j+1; i<=M; i++) { if( parent(edge[i].first) != parent(edge[i].second)) { cost += i; addTree(edge[i].first, edge[i].second); edgeCnt++; } if(edgeCnt == N-1) { break; } } if(edgeCnt!=N-1) { for(int k=j; k<K; k++) { printf("0 "); } break; } printf("%d ", cost); } } | cs |
댓글
댓글 쓰기