1944. 복제 로봇 


문제

세준이는 어느 날 획기적인 로봇을 한 개 개발하였다. 그 로봇은 복제 장치를 이용하면 자기 자신을 똑같은 로봇으로 원하는 개수만큼 복제시킬 수 있다. 세준이는 어느 날 이 로봇을 테스트하기 위하여 어떤 미로에 이 로봇을 풀어 놓았다. 이 로봇의 임무는 미로에 흩어진 열쇠들을 모두 찾는 것이다. 그리고 열쇠가 있는 곳들과 로봇이 출발하는 위치에 로봇이 복제할 수 있는 장치를 장착해 두었다.

N*N의 정사각형 미로(1≤N≤50)와 M개의 흩어진 열쇠(1≤M≤250)의 위치, 그리고 이 로봇의 시작 위치가 주어져 있을 때, 모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합을 최소로 하는 프로그램을 작성하여라. 로봇은 상하좌우 네 방향으로 움직이며, 로봇이 열쇠가 있는 위치에 도달했을 때 열쇠를 찾은 것으로 한다. (복제된 로봇이어도 상관없다) 하나의 칸에 동시에 여러 개의 로봇이 위치할 수 있으며, 로봇이 한 번 지나간 자리라도 다른 로봇 또는 자기 자신이 다시 지나갈 수 있다. 복제에는 시간이 들지 않으며, 로봇이 움직이는 횟수의 합은 분열된 로봇 각각이 움직인 횟수의 총 합을 말한다. 복제된 로봇이 열쇠를 모두 찾은 후 같은 위치로 모일 필요는 없다.

입력

첫째 줄에 미로의 크기 N(1<=N<=50)과 열쇠의 개수 M(1<=M<=250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어진다. 1은 미로의 벽을 의미하고, 0은 지나다닐 수 있는 길, S는 로봇이 출발하는 위치, K는 열쇠의 위치가 주어진다. S는 1개, K는 M개가 주어진다. S와 K에서만 복제를 할 수 있음에 유의한다.

출력

첫째 줄에 모든 로봇이 움직인 횟수의 총 합을 출력한다. 모든 열쇠를 찾는 것이 불가능한 경우 횟수 대신 첫째 줄에 -1을 출력하면 된다.

예제 입력 

5 2
11111
1S001
10001
1K1K1
11111

예제 출력 

6



1. 접근


S에서 시작해서 K로 가야한다. K에 도착하면 원하는 수만큼 자신을 복사할 수 있으며, 최종적으로 모든 K에 도착해야한다.

이 때 가장 적은 경로의 합을 구하는 문제다.


S와 K들 사이의 경로를 그래프처럼 그려보자.


예시 입력에는 2개의 K개 있으며 (K1, K2) S에서 K1으로 가는 비용은 2, K2는 4이다.


먼저 K1으로 가기로 해보고, 도착 한뒤 자아 분열을 통해 K2로 가는 비용은 4이다.


따라서 우리는 S와 K들 사이의 최소거리를 비용으로 하는 간선들로 이루어진 그래프로 문제를 이해할 수 있다.


그러면 문제에서 원하는 해답은 그래프의 어떤 모습이겠는가?


그래프를 최소신장트리화시켜 비용의 합을 원하는 문제임을 알 수 있다.



2. 풀이


최소거리를 먼저 구해서 간선화시키는 방법이 필요할 것이다. 이에 BFS를 차용한다.


매 S, K들 마다 BFS를 돌려서 간선들을 만들고 저장한다.


BFS시에 모든 K를 방문하지 못한다면 길이 없는 것이므로 -1을 출력한다.


그 후엔 디스조인트-셋을 활용한 크루스칼 알고리즘을 사용하면 된다.


키의 번호는 정해져 있지 않으므로, 각 좌표의 키 번호를 지정하고 저장할 배열이 필요할 것이다.


이후 저장된 간선들에 대해 정렬하고 크루스칼 알고리즘을 돌리자.


참고 : http://js1jj2sk3.tistory.com/22



3. 코드


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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
struct cd {
    int x, y;
};
cd start;
vector<cd> key_list;
 
struct edge {
    int weight, from, to;
};
bool cmp(const edge& e1, const edge& e2) {
    return e1.weight < e2.weight;
}
vector<edge> E;
 
int n, m, i, j, cx, cy, nx, ny, cnt, sum;
int key_cnt, key_num[51][51];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int dist[51][51];
bool visit[51][51];
char map[51][51];
 
int parent[251];
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    parent[x] = y;
}
 
int bfs(int x, int y, int mom) {
    memset(visit, 0, sizeof(visit));
    memset(dist, 0, sizeof(dist));
    key_cnt = 1;
 
    queue<cd> q;
    q.push({ x,y });
    visit[x][y] = true;
 
    while (!q.empty()) {
        cx = q.front().x;
        cy = q.front().y;
        q.pop();
 
        for (i = 0; i < 4; ++i) {
            nx = cx + dir[i][0];
            ny = cy + dir[i][1];
 
            if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;
            if (visit[nx][ny] || map[nx][ny] == '1')
                continue;
 
            dist[nx][ny] = dist[cx][cy] + 1;
            visit[nx][ny] = true;
 
            if (map[nx][ny] == 'K') {
                key_cnt++;
                E.push_back({ dist[nx][ny], mom, key_num[nx][ny] });
            }
 
            if (key_cnt == key_list.size())
                return key_cnt;
 
            q.push({ nx,ny });
        }
    }
    return key_cnt;
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; ++i) {
        scanf("%s", map[i]);
        for (j = 0; j < n; ++j) {
            if (map[i][j] == 'S') {
                start = { i,j };
                map[i][j] = 'K';
            }
            if (map[i][j] == 'K') {
                key_list.push_back({ i,j });
                key_num[i][j] = ++key_cnt;
            }
        }
    }
 
    for (auto key : key_list) {
        if (bfs(key.x, key.y, key_num[key.x][key.y]) != key_list.size()) {
            puts("-1");
            return 0;
        }
    }
 
    sort(E.begin(), E.end(), cmp);
 
    for (i = 0; i <= key_list.size(); ++i)
        parent[i] = i;
 
    i = 0;
    while (cnt != key_list.size() - 1) {
        cx = find(E[i].from);
        cy = find(E[i].to);
 
        if (cx != cy) {
            unite(cx, cy);
            sum += E[i].weight;
            cnt++;
        }
        i++;
    }
    printf("%d", sum);
    return 0;
}
cs


'알고리즘 > Minimal spanning tree 최소신장트리' 카테고리의 다른 글

백준) 2887 행성 터널  (0) 2017.08.06
백준) 9372 상근이의 여행  (0) 2017.08.06
백준) 1647 도시 분할 계획  (0) 2017.08.06
백준) 1922 네트워크 연결  (0) 2017.08.06
백준) 1197 최소 스패닝 트리  (0) 2017.08.06

2887. 행성 터널


문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만드려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 

두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이 때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

예제 입력 

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

예제 출력 

4


1. 접근


모든 터널을 연결하는데 필요한 최소비용을 구하는 최소신장트리 문제이다.


크루스칼 알고리즘을 사용하자.



2. 풀이


간선을 고르는게 문제다.


A터널과 B터널의 연결은 x, y, z 좌표 중에 차이가 가장 작은 축으로 이루어진다.


단순히 N^2 으로 모든 터널을 만들어 본 다음에 크루스칼을 돌려볼 수 있지만, 시간제한이 문제다.



그러면 다음으로 떠오르는 생각은 정렬을 통해 N * log n 으로 해결할 방법을 찾아보는 것이다.


정렬이후 i, i - 1 행성의 차이로 터널을 만들어 보자. 그러면 총 3 * (N - 1) 개의 터널이 생길 것이다.


이 후 크루스칼을 돌리면 된다.



왜 이 방법이 최소신장트리의 모든 간선을 놓치지 않는 걸까?


단순히 x 축만 사용한다고 생각해보자. ( x = 0, 3, 4, 8, 13, 14 ) 


정렬 이후에 이웃 행성들 끼리만 터널을 만든다면 바로 0~14 까지 일렬로 쭈욱 터널이 생긴다.

바로 최소신장트리를 만들 수 있다. 이 간선들 외에 다른 최소신장 트리를 만드는 방법은 없다.


따라서 축을 세 개 쓴다고 해도 이는 변하지 않는다.

다만 쓸데 없는 간선이 2 * (N - 1)개 추가될 뿐이다.


정답인 N - 1 개의 간선은 놓쳐지지 않고 포함된다.


참고 : http://js1jj2sk3.tistory.com/22



3. 코드


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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
 
struct planet {
    int x, y, z, num;
};
bool cmpx(const planet& p1, const planet& p2) {
    return p1.x > p2.x;
}
bool cmpy(const planet& p1, const planet& p2) {
    return p1.y > p2.y;
}
bool cmpz(const planet& p1, const planet& p2) {
    return p1.z > p2.z;
}
planet pl[100000];
 
struct edge {
    int weight, from, to;
};
bool operator<(const edge& e1, const edge& e2) {
    return e1.weight > e2.weight;
}
vector<edge> ed;
 
 
int parent[100000];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
 
    parent[x] = y;
}
 
int n, i;
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d %d %d", &pl[i].x, &pl[i].y, &pl[i].z);
        pl[i].num = i;
        parent[i] = i;
    }
 
    sort(pl, pl + n, cmpx);
    for (i = 0; i < n - 1; ++i)
        ed.push_back({ abs(pl[i].x - pl[i + 1].x), pl[i].num, pl[i + 1].num });
 
    sort(pl, pl + n, cmpy);
    for (i = 0; i < n - 1; ++i)
        ed.push_back({ abs(pl[i].y - pl[i + 1].y), pl[i].num, pl[i + 1].num });
 
    sort(pl, pl + n, cmpz);
    for (i = 0; i < n - 1; ++i)
        ed.push_back({ abs(pl[i].z - pl[i + 1].z), pl[i].num, pl[i + 1].num });
 
    sort(ed.begin(), ed.end());
 
    int ans = 0;
    int cnt = 0;
    for (int i = ed.size() - 1; cnt != n - 1;--i) {
        if (find(ed[i].from) != find(ed[i].to)) {
            cnt++;
            ans += ed[i].weight;
 
            unite(ed[i].from, ed[i].to);
        }
        if (cnt == n - 1)
            break;
    }
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > Minimal spanning tree 최소신장트리' 카테고리의 다른 글

백준) 1944 복제 로봇  (0) 2017.08.06
백준) 9372 상근이의 여행  (0) 2017.08.06
백준) 1647 도시 분할 계획  (0) 2017.08.06
백준) 1922 네트워크 연결  (0) 2017.08.06
백준) 1197 최소 스패닝 트리  (0) 2017.08.06

9372. 행성 터널


문제

상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 

하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.

이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 도시들을 여행할 수 있도록 도와주자.

상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

입력

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,

각 테스트 케이스마다 다음과 같은 정보가 주어진다.

  • 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
  • 이후 M개의 줄에 a와 b 쌍들이 입력된다. (a와 b를 왕복하는 비행기가 있다는 것을 의미한다)
  • 주어지는 비행 스케줄은 항상 연결 그래프(Connected Graph)를 이룬다.

출력

테스트 케이스마다 한 줄을 출력한다.

  • 상근이가 모든 도시를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.

예제 입력 

2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5

예제 출력 

2
4



1. 접근


번역이 좀 애매하게 되어있지만, 가장 적은 종류의 비행기란 결국 최소신장트리를 구하라는 뜻과 일맥상통한다.


원문에는 가장 기장을 적게 알게 되면서 모든 도시를 방문하는 기장 수를 출력하라고 되어있다.


비행기를 처음 타면 기장과 안면을 트게 되고, 다시 타도 알던 사이이므로 상관없다. 즉 간선을 가장 적게 포함하는 트리를 만들어야 한다.

 


2. 풀이


간선의 비용을 모두 같다고 해보자. 그러면 우리가 만들어야 하는 최소신장트리다.


허나 우리는 이미 최소신장트리의 간선 수를 알고 있다. n - 1 이므로 바로 출력해주자.


참고 : http://js1jj2sk3.tistory.com/22



3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
using namespace std;
 
int t, v, e, a, b, i;
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &v, &e);
        for (i = 0; i < e; ++i) {
            scanf("%d %d", &a, &b);
        }
        printf("%d\n", v - 1);
    }
    return 0;
}
cs


'알고리즘 > Minimal spanning tree 최소신장트리' 카테고리의 다른 글

백준) 1944 복제 로봇  (0) 2017.08.06
백준) 2887 행성 터널  (0) 2017.08.06
백준) 1647 도시 분할 계획  (0) 2017.08.06
백준) 1922 네트워크 연결  (0) 2017.08.06
백준) 1197 최소 스패닝 트리  (0) 2017.08.06

1647. 도시 분할 계획


문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C라는 뜻이다.

출력

첫째 줄에 없애고 남은 길 유지비의 합의 최소값을 출력한다.

예제 입력 

7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

예제 출력 

8



1. 접근


마을 안에 길이 너무 많아서 최소신장트리로 만들려고 한다.


단 마을을 둘로 나누고자 한다. 즉, 트리를 두개로 나누려고 하는 것이다.


최소신장트리이니 일단 크루스칼 알고리즘을 쓰기로 한다.



2. 풀이


일단 마을을 최소신장트리로 만들어보자.


그러면 길은 N - 1개일 것이다. 이 트리에서 간선을 하나 제거해서 한 집을 똑 떼어놓아 보자.


그러면 기존의 트리는 N - 2개의 길로 이루어졌고, N - 1개를 포함하는 최소신장트리이다.


당연히 떨어진 집은 자체로도 마을이고 최소신장트리이다.


그러면 제거할 간선의 기준은 어떻게 되겠는가? 트리 중 가장 큰 간선이다.


이 간선은 또한 크루스칼 알고리즘의 가장 마지막에 합류한 간선이다.


따라서 길을 N - 2개 까지만 크루스칼 알고리즘을 진행해도 같은 결과를 얻을 수 있다.



마을을 두개로 나누는 방법은 여러가지이지만, 간선의 수 (N-2) 는 동일하다.


따라서 가장 큰 간선을 제거하는 위의 방법이 최소임은 보장된다.


참고 : http://js1jj2sk3.tistory.com/22



3. 코드


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
struct edge {
    int weight, from, to;
};
bool operator<(const edge& e1, const edge& e2) {
    return e1.weight < e2.weight;
}
edge E[1000001];
 
int v, e, a, b, c, i, cnt, sum;
int parent[100001];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void unite(int x, int y) {
    x = parent[x];
    y = parent[y];
    parent[x] = y;
}
 
int main() {
    scanf("%d %d", &v, &e);
    for (i = 0; i < e; ++i) {
        scanf("%d %d %d", &a, &b, &c);
        E[i] = { c,a,b };
    }
    for (i = 1; i <= v; ++i)
        parent[i] = i;
    sort(E, E + e);
 
    i = 0;
    while (cnt != v - 2) {
        a = E[i].from;
        b = E[i].to;
        if (find(a) != find(b)) {
            unite(a, b);
            cnt++;
            sum += E[i].weight;
        }
        i++;
    }
    printf("%d", sum);
    return 0;
}
cs


'알고리즘 > Minimal spanning tree 최소신장트리' 카테고리의 다른 글

백준) 2887 행성 터널  (0) 2017.08.06
백준) 9372 상근이의 여행  (0) 2017.08.06
백준) 1922 네트워크 연결  (0) 2017.08.06
백준) 1197 최소 스패닝 트리  (0) 2017.08.06
최소신장트리 도입  (0) 2017.08.06

1922. 네트워크 연결


문제

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수(1<=N<=1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수(1<=M<=100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c만큼 든다는 것을 의미한다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

예제 입력 

6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
3 5 11
4 5 3
4 6 8
5 6 8

예제 출력 

23



1. 접근


최소신장트리를 구해야 한다.


http://js1jj2sk3.tistory.com/23와 동일하다.


크루스칼 알고리즘을 사용하자.



2. 풀이


사이클의 유무를 확인하는데 디스조인트-셋을 사용한다.


참고 : http://js1jj2sk3.tistory.com/22



3. 코드


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
struct edge {
    int weight, from, to;
};
bool operator<(const edge& e1, const edge& e2) {
    return e1.weight < e2.weight;
}
edge E[100001];
 
int v, e, a, b, c, i, cnt, sum;
int parent[1001];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void unite(int x, int y) {
    x = parent[x];
    y = parent[y];
    parent[x] = y;
}
 
int main() {
    scanf("%d %d", &v, &e);
    for (i = 0; i < e; ++i) {
        scanf("%d %d %d", &a, &b, &c);
        E[i] = { c,a,b };
    }
    for (i = 1; i <= v; ++i)
        parent[i] = i;
    sort(E, E + e);
 
    i = 0;
    while (cnt != v - 1) {
        a = E[i].from;
        b = E[i].to;
        if (find(a) != find(b)) {
            unite(a, b);
            cnt++;
            sum += E[i].weight;
        }
        i++;
    }
    printf("%d", sum);
    return 0;
}
cs


'알고리즘 > Minimal spanning tree 최소신장트리' 카테고리의 다른 글

백준) 2887 행성 터널  (0) 2017.08.06
백준) 9372 상근이의 여행  (0) 2017.08.06
백준) 1647 도시 분할 계획  (0) 2017.08.06
백준) 1197 최소 스패닝 트리  (0) 2017.08.06
최소신장트리 도입  (0) 2017.08.06

1197. 최소 스패닝 트리


문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1≤V≤10,000)와 간선의 개수 E(1≤E≤100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않는다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 

3 3
1 2 1
2 3 2
1 3 3

예제 출력 

3



1. 접근


대놓고 최소스패닝트리를 찾으라고 써있는 문제.


크루스칼 알고리즘을 쓰자.



2. 풀이


간선들을 가중치 순으로 정렬하자.

가장 작은 간선부터 보면서 추가시 사이클이 생기지 않는다면 추가해 준다.

사이클의 유무는 디스조인트-셋 으로 확인해준다. 루트 노드가 같다면 연결되어 있다는 뜻이고, 추가하면 사이클이 생겨버린다.


가중치의 합만 구하면 되므로, 간선의 순서를 기억하지 않아도 좋다.


다음을 참고 : http://js1jj2sk3.tistory.com/22


3. 코드


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int v, e, a, b, c, i, cnt, sum;
struct edge {
    int weight, from, to;
};
bool operator<(const edge& e1, const edge& e2) {
    return e1.weight < e2.weight;
}
edge E[100001];
 
int parent[100001];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void unite(int x, int y) {
    x = parent[x];
    y = parent[y];
    parent[x] = y;
}
 
int main() {
    scanf("%d %d", &v, &e);
    for (i = 0; i < e; ++i) {
        scanf("%d %d %d", &a, &b, &c);
        E[i] = { c,a,b };
    }
    for (i = 1; i <= v; ++i)
        parent[i] = i;
    sort(E, E + e);
 
    i = 0;
    while (cnt != v - 1) {
        a = E[i].from;
        b = E[i].to;
        if (find(a) != find(b)) {
            unite(a, b);
            cnt++;
            sum += E[i].weight;
        }
        i++;
    }
    printf("%d", sum);
    return 0;
}
cs

4

4. 후기


구조체를 algorithm : sort에 적용시키는 방법을 기억해두자. 연산자 오버로딩이 필요하다.

'알고리즘 > Minimal spanning tree 최소신장트리' 카테고리의 다른 글

백준) 2887 행성 터널  (0) 2017.08.06
백준) 9372 상근이의 여행  (0) 2017.08.06
백준) 1647 도시 분할 계획  (0) 2017.08.06
백준) 1922 네트워크 연결  (0) 2017.08.06
최소신장트리 도입  (0) 2017.08.06

1. 최소신장트리란?


트리는 그래프의 노드들과 모든 노드간의 관계를 나타내는 간선들로 이루어진다.


최소신장트리란, 당연하게도 신장트리들 중에 가장 작은 규모의 트리를 말한다.


신장트리란 주어진 그래프의 모든 노드를 포함하면서, 모든 노드간에 관계가 있는(경로가 있는) 트리를 말한다.

다만 사이클은 포함하지 않아야 한다. 


규모라는 의미는, 간선들의 크기와 수에 비례하는 척도다.


따라서 최소신장트리는 신장트리를 만드는 여러 경우들 가운데 간선들의 크기(비용)의 합이 가장 작은 경우를 말한다.(사이클 미포함)




2. 최소신장트리를 구하는 알고리즘


그렇다면 최소신장트리를 어떻게 구할 수 있을까?


먼저 대표적인 알고리즘으로 크루스칼 알고리즘이 있다.


크루스칼 알고리즘의 흐름은 다음과 같다.


1) 간선들을 비용이 작은 순으로 정렬한다.

2) 가장 작은 간선부터 신장트리로 포함시킨다.(단 포함시키면 사이클이 생겨버리는 간선은 포함시키지 않는다.)

3) 모든 정점이 연결되지 않았다면 2단계로 돌아간다.


3단계로 보아 모든 정점이 포함될 것은 자명하고, 2단계의 제약조건으로 보아 사이클은 생기지 않을 것이다.

따라서 결과물이 신장트리가 될 것은 분명하다. 하지만 그 신장트리는 가장 작은 신장트리인가?


크루스칼 알고리즘이 최소신장트리를 찾는다는 증명은 다음과 같다.


우리는 다음을 귀납적으로 증명할 것이다 :

"알고리즘의 2단계를 수행하고 난 뒤 골라진 간선들의 집합을 F라고 하면, 항상 F를 포함하는 최소신장트리가 있다"


1단계에선 F는 빈 집합이다. 당연히 F를 포함하는 신장트리가 있다.

2단계는 반복적으로 수행된다. 다음에 2단계가 수행되면서 간선 e가 포함된다.

(F+e) 이 집합을 포함하는 최소신장트리가 있음을 보여야 한다.

e는 정답인 최소신장트리의 간선일 수도, 아닐 수도 있다. 맞다면 잘한 것이나, 아닐 경우 문제가 있다.


e가 노드 a, b를 잇는 간선이라고 해보자. 또한 원래 정답인 최소신장트리 또한 a에서 b로가는 경로를 유일하게 갖고 있다.

헌데 e를 추가함으로써 (F+e)는 사이클을 갖게된다. 이는 규칙에 어긋나므로 e가 정답의 일부임을 증명하였다.


두 번째 알고리즘으로 프림 알고리즘이 있다.


크루스칼 알고리즘이 최소신장트리를 이곳 저곳 따로 완성시켜나가는 반면, 프림은 한 지점부터 확장시켜나가면서 완성시킨다.


1) 아무 노드나 시작점으로 정한다.(A)

2) 그 노드에 연결된 간선 중 비용이 가장 작은 간선(A-B)을 포함시킨다. 단 B는 지금까지 연결되지 않은 노드이다.

3) A, B 아무 노드나 정하고 2를 반복한다.


최소신장트리를 완성해 나가는 과정은 선형시간에 가능하다.(크루스칼의 사이클을 확인하는 과정은 디스조인트-셋으로 간소화된다)

시간을 잡아먹는 작업은 가장 비용이 작은 간선을 찾는 작업에서 비롯된다.

크루스칼은 처음에 모든 간선을 정렬해야 하고, 프림은 각 단계의 노드와 연결된 간선들을 정렬해야한다.


따라서 시간 복잡도는 다음과 같다. 




3. 최소신장트리를 구해야 하는 문제들



1) 1197 최소 스패닝 트리 : https://www.acmicpc.net/problem/1197


말 그대로인 문제.


풀이 : http://js1jj2sk3.tistory.com/23


2) 1922 네트워크 연결 : https://www.acmicpc.net/problem/1922


모든 노드를 연결하는 최소비용을 구해야 한다. 최소신장트리의 정의를 알고 있는지 묻고 있다.


풀이 : http://js1jj2sk3.tistory.com/24


3) 1647 도시 분할 계획 : https://www.acmicpc.net/problem/1647


그래프를 두 최소신장트리로 나누려고 한다. 최소신장트리의 간선 수는 (노드의 수(n) - 1)임을 생각해보자.


풀이 : http://js1jj2sk3.tistory.com/25


4) 9372 상근이의 여행 : https://www.acmicpc.net/problem/9372


가장 적은 종류의 비행기를 탄다 = 가장 간선의 수가 적은 트리는 ? = 최소신장트리


풀이 : http://js1jj2sk3.tistory.com/26


5) 2887 행성 터널 : https://www.acmicpc.net/problem/2887


최소신장트리를 구해야 하는 문제임은 명확하지만, 간선이 모호하게 주어졌다. 


풀이 : http://js1jj2sk3.tistory.com/27


6) 1944 복제 로봇 : https://www.acmicpc.net/problem/1944


어느 지점을 노드화 시키고, 간선의 비용은 어떻게 구할 것인지가 중요하다.


풀이 : http://js1jj2sk3.tistory.com/28

'알고리즘 > Minimal spanning tree 최소신장트리' 카테고리의 다른 글

백준) 2887 행성 터널  (0) 2017.08.06
백준) 9372 상근이의 여행  (0) 2017.08.06
백준) 1647 도시 분할 계획  (0) 2017.08.06
백준) 1922 네트워크 연결  (0) 2017.08.06
백준) 1197 최소 스패닝 트리  (0) 2017.08.06

+ Recent posts

티스토리툴바