컴퓨터 N를 최소의 비용으로 연결하기 위해서는 사이클이 생성되도록 연결하면 번복된 연결이 발생하므로 

사이클이 발생하지 않도록 모든 컴퓨터들이 연결되도록 하는 문제로 이해했다. 

입력 -> 정점 V1, V2 가중치 W로  vector에  적재하여 가중치 w를 기준으로 오름차순 정렬을 한뒤에 

Disjoint_Set을 사용하여 사이클 발생여부를 판단하면서 가중치를 더해주면 끝

Disjoint_Set이나 Mst를 숙지하고 있다면 굉장히*3  쉽게 풀수 있는 문제입니다.


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






<code>


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
// pda_pro12
#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 0x7fff0000
#define N_ 100000
using namespace std; 
 
int n, m, par[N_], ans; 
vector<pair<int, pair<int, int>>> v; 
 
int find(int x) {
    if (x == par[x])
        return x; 
    return par[x] = find(par[x]); 
}
 
bool Merge(int x, int y) {
    x = find(x); 
    y = find(y); 
    if (x == y)
        return false; 
    par[y] = x; 
    return true; 
}
 
int main() {
    int v1, v2, w;
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);   
 
    cin >> n >> m; 
    for (int i = 1; i <= n; i++)
        par[i] = i; 
    
    while (m--) {
        cin >> v1 >> v2 >> w; 
        v.push_back({ w, {v1, v2}}); 
    }
    sort(v.begin(), v.end());    // 가중치 별 정렬 
    
    for (int i = 0; i < v.size(); i++) {
        int w = v[i].first; 
        int v1 = v[i].second.first; 
        int v2 = v[i].second.second; 
        if (Merge(v1, v2))  // 사이클 발생하지 않을경우 연결 후  
            ans += w;    // 연결비용 적재 
    }
    cout << ans; 
    return 0; 
}


저작자표시

  




3개월전쯤이었나 이분탐색 문제들중에서 유일하게 못풀었던 문제였다. 


그냥 못풀겠거니~ 하고 냅뒀는데 북마크 문제 뒤적이다가 한번 볼까하고 풀었는데 

인덱스 카운팅을 통해 풀수 있을것 같았다.


-> 석순은 최대 높이부터 아래로 탐색하면서 보다 높은 높이에서 뚫어야할 석순이 있다면 그것보다 낮은 높이에도 뚫어야할게 있는것이므로 1높은 높이에서의 정보를 그대로 가저옴으로서 (종유석도 마찬가지) 종유석과 석순에 대한 뚫어야할 갯수 정보를 저장한다. 

갱신된 석순과 종유석을 기반으로 높이 하나하나(1~ h)까지의 관점에서 종유석과 석순의 뚤어야할 갯수를 더하며 정해를 찾아낸다.





<code>


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
// pda_pro12
#include<iostream>
 
#define N_ 500001
#define D 0x7fffffff
 
using namespace std;
 
int s[N_], r[N_], s_b[N_], s_t[N_], n, h, min_ = D, cnt_; 
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL), cout.tie(NULL); 
    cin >> n >> h; 
    for (int i = 0; i < n / 2; i++) {
        int t, b; 
        cin >> b >> t; 
        s_b[b]++; s_t[t]++; 
    }
    for (int i = h; i >= 1; i--) {   // 가장 높은 높이부터 
        s[i] = s_b[i] + s[i + 1]; s_b[i] = 0; 
        r[i] = s_t[i] + r[i + 1]; 
    }
    for (int i = 1; i <= h; i++) {
        s_b[i] = s[i] + r[h - i + 1]; 
        if (s_b[i] <= min_)
            (s_b[i] == min_) ? cnt_++ : cnt_ = 1, min_ = s_b[i]; 
    }
    cout << min_ << ' ' << cnt_; 
    return 0;
}


저작자표시


문제 설명에서 가장 먼거리에 숨은 헛간의 번호를 찾는다고 하였으나 사실상 시작점으로 부터
각 헛간까지 우회하는 경로가 없어야하므로, 다익스트라로 각 헛간까지의 최단거리를 
갱신해주면된다. 

중요한것은 거리를 기준으로 정렬하였을때, 초기 입력받은 번호에 대한 정보를 잃지 않기 위해서 

구조체 형식으로 거리배열을 생성하고, 갱신하였다. 

나머지는 무방향 그래프이면서 최대거리와 최대거리 요소의 갯수만 찾아주면 간단히 해결된다.



<code>

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
//pda_pro12
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
 
#define all(x) x.begin(), x.end()
#define INT 0x7fffffff
#define N_ 20001
 
using namespace std;
 
struct DATA { int num, value; };
 
vector<pair<int, int>> v[N_]; priority_queue<pair<int, int>> pq;
int n, m; DATA dst[N_]; int x, y; vector<int> ans;
 
bool cmp(DATA u, DATA t) {
    return u.value < t.value;
}
bool cmp1(DATA u, DATA t) {
    return u.num < t.num;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    while (m--) {
        cin >> x >> y;
        v[x].push_back({ y, 1 });
        v[y].push_back({ x, 1 });
    }
    for (int i = 1; i <= n; i++) {
        dst[i].value = INT, dst[i].num = i;
    }
    dst[1].value = 0;
    pq.push({ 1, 0 });
    while (!pq.empty()) {
        int v_x = pq.top().first;
        int dis = -pq.top().second;
        pq.pop();
        if (dis > dst[v_x].value) continue;
        for (int i = 0; i < v[v_x].size(); i++) {
            int next = v[v_x][i].first;
            int n_dis = dis + v[v_x][i].second;
            if (n_dis < dst[next].value) {
                dst[next].value = n_dis;
                pq.push({ next, -n_dis });
            }
        }
    }
    sort(dst + 1, dst + 1 + n, cmp);
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        if (Max < dst[i].value) {
            Max = dst[i].value;
            ans.clear();
            ans.push_back(dst[i].num);
        }
        else if (Max == dst[i].value)
            ans.push_back(dst[i].num);
    }
    sort(all(ans));
    cout << ans.front() << ' ' << Max << ' ' << ans.size();
 
    return 0;
}


저작자표시

'PS) BOJ > Dijkstra' 카테고리의 다른 글

[C++]알고스팟[백준1261]  (0) 2018.08.15

+ Recent posts

티스토리툴바