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

같은 의미로는 두 직선이 주어졌을 때 그 사이의 각도를 구하는 것

 

세점 A,B,C 가 있고

각 점은 구조체로써 x, y좌표를 가지고 있다면 

angle(A,B,C) -> 점 B를 중심으로 하는 점 A, B, C 사이의 각도를 구할 수 있다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct poly {
   lld x, y;
};
 
#define M_PI 3.14159
 
double angle(poly& a, poly& b, poly& c) {
    double aa, bb, cc;
    double ang, temp;
 
    aa = sqrt(pow(a.x - c.x, 2) + pow(a.y - c.y, 2));
    bb = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
    cc = sqrt(pow(b.x - c.x, 2) + pow(b.y - c.y, 2));
 
    temp = (pow(bb, 2) + pow(cc, 2) - pow(aa, 2)) / (2 * bb * cc);
    ang = acos(temp);
    ang = ang * (180 / M_PI);
 
    return ang;
}
 

 

 

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

전위 중위 후위 순회방법  (0) 2020.04.24
전위, 중위 정보로 트리 만들기  (0) 2020.04.24
STL 사용할때 주의할 것(set,map,...)  (0) 2020.04.10
Point in a Polygon - 다각형 내부점 판단  (0) 2020.04.07
좌표 시계/반시계방향 정렬  (0) 2020.04.07

가끔 코딩하다가 하는 실수인데,

typedef 로 여러 자료형을 묶어서 사용하면서

 

C++ 인수 목록이 일치하는 오버로드된 함수의 인스턴스가 없습니다

오류 C2676 이항 '<': 'const _Ty1'이(가) 이 연산자를 정의하지 않거나 미리 정의된 연산자에 허용되는 형식으로의 변환을 정의하지 않습니다.

 

등등의 오류를 볼 수 있다.

 

이 때, 오류의 원인은 아무리 set이나 map의 형식에 맞게 사용했어도

연산자체가 불가능한 값(또는 형태)을 넣었기 때문이다.

 

set, map 등등의 STL은 내부에서 비교연산이 이루어지는데,

다음 코드를 통해 연산이 가능한 경우와 불가능한 경우를 살펴보고 실수하지 말자

1
2
3
4
5
6
struct poly {
    int x, y;
};
set<pair<pair<poly, poly>, int> > visit; // 안되는 경우
typedef pair<int,int> pii2;
set<pair<pair<pii2, pii2>, int> > visit; // 되는 경우

 

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

전위, 중위 정보로 트리 만들기  (0) 2020.04.24
c,c++ 세 점이 주어졌을 때 각도 구하기  (0) 2020.04.10
Point in a Polygon - 다각형 내부점 판단  (0) 2020.04.07
좌표 시계/반시계방향 정렬  (0) 2020.04.07
bit masking (비트마스킹 정리)  (0) 2020.03.14

+ Recent posts

티스토리툴바