BOJ : https://www.acmicpc.net/problem/1922

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
typedef pair<int, int> pii;
vector<pii> v[1005];
bool visit[1005];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int N, M;
 
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({ c,b });
        v[b].push_back({ c,a });
    }
 
    priority_queue<pii, vector<pii>, greater<pii> > q;
    visit[1] = true;
    for (int i = 0; i < v[1].size(); i++) q.push({ v[1][i].first, v[1][i].second });
    int cnt = N - 1;
    int ret = 0;
    while (cnt) {
        int w = q.top().first;
        int n = q.top().second;
        q.pop();
        if (visit[n]) continue;
        visit[n] = true;
        ret += w;
        cnt--;
        for (int i = 0; i < v[n].size(); i++) if (!visit[v[n][i].second]) q.push({ v[n][i].first, v[n][i].second });
    }
    cout << ret;
 
    return 0;
}
 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 14750번 Jerry and Tom  (0) 2020.04.28
BOJ 1647번 도시 분할 계획  (0) 2020.04.11
BOJ 1197번 최소 스패닝 트리  (0) 2020.04.10
BOJ 2699번 격자점 컨벡스헐  (0) 2020.04.07
BOJ 1708번 볼록 껍질  (0) 2020.04.07

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

 

MST 는 알려진 알고리즘이 프림, 크루스칼이 있다

 

크루스칼은 모든 간선을 기준으로 가중치가 작은거부터 뽑아서 사이클이 형성되는지 안되는지 확인해가는 방법이다

사이클이 형성되는지 확인하는 방법은 배열을 통해 부모를 저장해가면서 집합의 개념을 사용하는 방법이 있다

 

프림은 아무 정점이나 시작점으로 잡고 간선을 1개씩 연결해가면서 가장 작은 가중치를 가진 간선을 뽑아서 연결해간다

가장 작은 가중치를 빠른시간내에 뽑는 방법은 우선순위큐를 사용하는 방법이 있다

 

프림 알고리즘으로 해결한 코드

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
typedef pair<int, int> pii;
int Vn, En;
vector<pii> v[10002];
bool visit[10001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> Vn >> En;
    for (int i = 0; i < En; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
        v[e].push_back({ s,w });
    }
 
    long long answer = 0;
    int cnt = Vn - 1;
    priority_queue<pii, vector<pii >, greater<pii> > q;
 
    for (int i = 0; i < v[1].size(); i++) {
        q.push({ v[1][i].second,v[1][i].first });
    }
    visit[1] = true;
    while (cnt) {
        int now = q.top().second;
        int w = q.top().first;
        q.pop();
        if (visit[now]) continue;
        visit[now] = true;
        answer += w;
        cnt--;
        for (int i = 0; i < v[now].size(); i++) {
            if (!visit[v[now][i].first]) q.push({ v[now][i].second, v[now][i].first });
        }
    }
 
    cout << answer;
 
    return 0;
}
 

 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1647번 도시 분할 계획  (0) 2020.04.11
BOJ 1922번 네트워크 연결  (0) 2020.04.11
BOJ 2699번 격자점 컨벡스헐  (0) 2020.04.07
BOJ 1708번 볼록 껍질  (0) 2020.04.07
BOJ 1063번 킹  (0) 2020.04.07

BOJ : https://www.acmicpc.net/problem/2699

 

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 <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
struct point {
    int x, y;
    int p = 0, q = 0;
}p[52];
 
bool cmp(point& a, point& b) {
    if (a.p * b.q != a.q * b.p) return a.q * b.p > a.p * b.q;
    if (a.y != b.y) return a.y > b.y;
    return a.x < b.x;
}
 
int ccw(point& a, point& b, point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int tc; cin >> tc;
 
    while (tc--) {
        int N; cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> p[i].x >> p[i].y;
            p[i].p = p[i].q = 0;
        }
        sort(p, p + N, cmp);
        for (int i = 1; i < N; i++) {
            p[i].p = p[i].x - p[0].x;
            p[i].q = p[i].y - p[0].y;
        }
        sort(p + 1, p + N, cmp);
        stack<int> s;
        s.push(0), s.push(1);
        int next = 2;
        while (next < N) {
            while (s.size() >= 2) {
                int second = s.top();
                s.pop();
                int first = s.top();
                if (ccw(p[first], p[second], p[next]) < 0) {
                    s.push(second);
                    break;
                }
            }
            s.push(next++);
        }
        cout << s.size() << endl;
        vector<point> v;
        while (!s.empty()) {
            v.push_back(p[s.top()]);
            s.pop();
        }
        for (int i = v.size() - 1; i >= 0; i--) cout << v[i].x << " " << v[i].y << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1922번 네트워크 연결  (0) 2020.04.11
BOJ 1197번 최소 스패닝 트리  (0) 2020.04.10
BOJ 1708번 볼록 껍질  (0) 2020.04.07
BOJ 1063번 킹  (0) 2020.04.07
BOJ 14499번 주사위 굴리기  (0) 2020.03.14

BOJ : https://www.acmicpc.net/problem/1708

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
struct point {
    ll x, y;
    ll p = 0, q = 0;
}p[100001];
 
bool cmp(point& a, point& b) {
    if (1LL * a.p * b.q != 1LL * a.q * b.p) return a.q * b.p < a.p * b.q;
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
 
ll ccw(point& a, point& b, point& c) {
    return 1LL * (b.x - a.x) * (c.y - a.y) - 1LL * (b.y - a.y) * (c.x - a.x);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int N; cin >> N;
    for (int i = 0; i < N; i++) cin >> p[i].x >> p[i].y;
 
    sort(p, p + N, cmp);
    for (int i = 1; i < N; i++) {
        p[i].p = p[i].x - p[0].x;
        p[i].q = p[i].y - p[0].y;
    }
    sort(p + 1, p + N, cmp);
    stack<int> s;
    s.push(0), s.push(1);
    int next = 2;
    while (next < N) {
        while (s.size() >= 2) {
            int second = s.top();
            s.pop();
            int first = s.top();
            if (ccw(p[first], p[second], p[next]) > 0) {
                s.push(second);
                break;
            }
        }
        s.push(next++);
    }
    cout << s.size();
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1197번 최소 스패닝 트리  (0) 2020.04.10
BOJ 2699번 격자점 컨벡스헐  (0) 2020.04.07
BOJ 1063번 킹  (0) 2020.04.07
BOJ 14499번 주사위 굴리기  (0) 2020.03.14
BOJ 14503번 로봇 청소기  (0) 2020.03.13

+ Recent posts

티스토리툴바