백준의 도시분할계획(1647) 문제이다.

[ 문제 바로가기 ]


[ 문제풀이 ]

1) 이 문제는 MST를 만들어야 하는 문제이다. 따라서, 크루스칼 알고리즘을 이용해서 MST를 만들어야 하는데, 아직

   크루스칼 알고리즘에 대해서 잘 모른다면 아래의 링크를 타고 크루스칼에 대해서 알아보고 오도록 하자.

   [ 크루스칼 알고리즘 개념 및 구현방법 알아보기 ]

  

   위의 글을 읽었다면 ,기본적인 크루스칼의 개념과 구현방식에 대해서 충분히 이해했을거라 생각한다. 그럼 문제를 풀자 !


   문제를 다시한번 읽고, 문제에서 제시한 조건을 먼저 문제에서 찾아보고, 해결법도 알아보도록 하자.

   1. "마을의 이장은 마을을 두개의 분리된 마을로 분할할 것이다."

   2. "각 마을에는 집이 하나 이상 있어야 한다."

   3. "분리된 마을 안에서도 두 집 사이의 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다."

   4. "위의 조건을 만족하도록 길을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다."

   본인이 생각하는 문제에서 제시해준, 구현에 대한 조건 4가지이다.

   먼저 3번과, 4번부터 보자. 3번과 4번을 보면, MST를 구현하면 되겠다는 것을 우리는 알 수 있다.

   1번조건을 한번 보자.

   마을을 2개의 분리된 마을로 분할해야 한다고 하였다. 즉, 우리는 최소 스패닝 트리를 만들어야 하는데, 모든 정점을 이용

   하는 것이 아니라, 일부 정점을 빼줘야 한다는 의미이다. 그래야지 최소 스패닝 트리가 2개가 나오기 때문이다.

  

   그렇다면, 어떻게 해야 모든 길들의 합이 최소가 될까??

   바로 최대 가중치로 연결되어 있는 집을 하나 분리해버리면 된다. 최대 가중치가 아닌 그보다 더 작은 가중치로 연결되어

   있는 집을 제외했다고 생각해보자. 당연히, 그 길들의 합이 최소가 될리가 없다.

   즉, 우리는 최대 가중치로 연결되어 있는 집을 하나 분리해버리면 된다.

  

2) 그렇다면, 1)에서 말한 방법을 크루스칼 알고리즘에서 어떻게 적용시켜야 할지, 어느 부분을 바꿔줘야 할지 알아보자.

   앞에서 말했듯이, 가장 최대 가중치로 연결된 간선만 빼주면 그게 최소값이 될 것이다.

   크루스칼 알고리즘은 가중치들을 오름차순으로 정렬 후에 가장 작은 가중치들부터 연결해 나가는 방식이다.

   즉, 가장 마지막에 연결된 가중치만 빼주면 된다는 의미이다.

   이 부분을 구현하기 위해서 본인은 Vector를 하나 더 사용해서 가중치들만 저장해주었다. 이 후, 가중치들을 모두

   더해주는데, 이 때 여기서 만든 Vector의 size만큼이 아닌 size() - 1 만큼 실행시켜 주었다.

   size() - 1만큼 실행한다는 것의 의미는, 가장 마지막에 추가된 간선은 전체비용에 포함하지 않겠다는 의미이고, 이는

   가장 큰 가중치를 가진 간선을 제외한 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 100000 + 1
using namespace std;
 
int N, M, Answer;
int Parent[MAX];
vector < pair<intpair<intint>>> Edge;
vector<int> V;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        Edge.push_back(make_pair(c, make_pair(a, b)));
    }
}
 
int Find_Parent(int x)
{
    if (x == Parent[x]) return x;
    else return Parent[x] = Find_Parent(Parent[x]);
}
 
void Union(int x, int y, int Cost)
{
    x = Find_Parent(x);
    y = Find_Parent(y);
 
    if (x == y) return;
    Parent[y] = x;
    N--;
}
 
bool Same_Parent(int x, int y)
{
    x = Find_Parent(x);
    y = Find_Parent(y);
 
    if (x == y) return true;
    return false;
}
 
void Solution()
{
    sort(Edge.begin(), Edge.end());
    for (int i = 1; i <= N; i++) Parent[i] = i;
    
    for (int i = 0; i < Edge.size(); i++)
    {
        if (Same_Parent(Edge[i].second.first, Edge[i].second.second) == false)
        {
            Union(Edge[i].second.first, Edge[i].second.second, Edge[i].first);
            V.push_back(Edge[i].first);
        }
    }
 
    for (int i = 0; i < V.size() - 1; i++)
    {
        Answer = Answer + V[i];
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}
cs

  

  

  

+ Recent posts