반응형

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

 

22116번: 창영이와 퇴근

A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 격자를 입력받고, arr 배열에 저장합니다.

 

2. visited 배열을 만들어 해당 구간에 도착했을 때 경사로 차가 가장 적었을 때의 값을 저장합니다.

 

3. ans에 경사로 차 중 가장 큰 값을 저장합니다.

 

4. 다익스트라를 이용하여 경사로의 높이차가 작은 구간부터 방문하고, N - 1, N - 1 좌표에 도착하면 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int y, x, h;
};
 
struct cmp {
    bool operator()(node right, node left) {
        return left.h < right.h;
    }
};
 
int N;
int arr[1000][1000];
int visited[1000][1000];
int ans;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            visited[i][j] = 1111111111;
        }
    }
 
    priority_queue<node, vector<node>, cmp> pq;
    pq.push({ 0,0,0 });
    visited[0][0] = 0;
 
    while (!pq.empty()) {
        const int y = pq.top().y;
        const int x = pq.top().x;
        const int h = pq.top().h;
        pq.pop();
 
        if (visited[y][x] < h) continue;
 
        ans = max(ans, h);
 
        if (y == N - 1 && x == N - 1) {
            cout << ans;
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                int diff = abs(arr[y][x] - arr[yy][xx]);
                if (visited[yy][xx] > diff) {
                    visited[yy][xx] = diff;
                    pq.push({ yy,xx,diff });
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 20160번 - 야쿠르트 아줌마 야쿠르트 주세요 (C++)  (0) 2023.09.14
[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 3755번 - Double Queue (C++)  (0) 2023.09.11
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
반응형

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

 

4343번: Arctic Network

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열과 연결된 노드의 개수를 저장할 cnt를 선언합니다.

 

2. vect[ i ] = i로 초기화하고, 각 지점까지의 거리를  arr 배열에 저장합니다.

 

3. arr 배열을 거리를 기준으로 오름차순으로 정렬합니다.

 

4. Union-Find를 이용하여 각 지점들을 연결하고, 연결될 때마다 cnt++를 해주고, cnt == P - S일 때 거리를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int u, v;
    double d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int T, S, P;
vector<node> arr;
pair<int, int> pos[501];
int vect[501];
int cnt;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int u, int v)
{
    int pu = Find(u);
    int pv = Find(v);
 
    vect[pv] = pu;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    cout << fixed;
    cout.precision(2);
 
    for (int t = 0; t < T; t++) {
        cin >> S >> P;
 
        arr.clear();
        cnt = 0;
 
        for (int i = 1; i <= P; i++) {
            int x, y;
            cin >> x >> y;
            pos[i] = { x,y };
            vect[i] = i;
        }
 
        for (int i = 1; i <= P - 1; i++) {
            for (int j = i + 1; j <= P; j++) {
                int x = pos[i].first - pos[j].first;
                int y = pos[i].second - pos[j].second;
                double d = sqrt(x * x + y * y);
                arr.push_back({ i,j,d });
            }
        }
 
        sort(arr.begin(), arr.end(), cmp);
 
        for (auto& next : arr) {
            const int u = next.u;
            const int v = next.v;
            const double d = next.d;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                cnt++;
            }
 
            if (cnt == P - S) {
                cout << d << '\n';
                break;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
반응형

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

 

9879번: Cross Country Skiing

The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 <= M,N <= 500), each elevation being in the range 0 .. 1,000,000,000. Some of the cells in this grid are designated as waypoints for the course. The org

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 좌표를 i * N + j를 통해 번호를 매겨줍니다.

 

2. 지도를 입력받고, 모든 노드들의 상하좌우로 인접한 노드들의 이어 차이값을 arr 배열에 저장합니다.

 

3. waypoint의 개수를 cnt에 저장합니다.

 

4. arr 배열을 D를 기준으로 오름차순으로 정렬합니다.

 

5. arr 배열을 for문을 통해 돌면서 이어주고, 부모노드가 waypoint 라면  cnt--를 해주고, D의 최댓값을 ans에 저장합니다.

 

6. cnt == 0이라면 ans를 출력합니다

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
 
using namespace std;
 
struct node {
    int a;
    int b;
    int D;
};
 
bool cmp(node left, node right)
{
    return left.D < right.D;
}
 
int M, N;
int map[500][500];
vector<int> waypoint;
vector<node> arr;
int vect[250000];
int cnt = -1;
int dy[2] = { 1,0 };
int dx[2] = { 0,1 };
int ans;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &M, &N);
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
            vect[i * N + j] = i * N + j;
        }
    }
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            int num;
            scanf("%d", &num);
 
            if (num == 1) cnt++;
 
            waypoint.push_back(num);
        }
    }
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < 2; k++) {
                int ii = i + dy[k];
                int jj = j + dx[k];
 
                if (ii >= 0 && ii < M && jj >= 0 && jj < N) {
                    arr.push_back({ i * N + j, ii * N + jj, abs(map[i][j] - map[ii][jj]) });
                }
            }
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    for (auto& next : arr) {
        int pa = Find(next.a);
        int pb = Find(next.b);
        const int D = next.D;
 
        if (pa != pb) {
            if (waypoint[pa] == 1 && waypoint[pb] == 1) {
                cnt--;
            }
            else if (waypoint[pa] == 0 && waypoint[pb] == 1) {
                swap(pa, pb);
            }
 
            ans = max(ans, D);
 
            Union(pa, pb);
        }
 
        if (cnt == 0) {
            printf("%d", ans);
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18
[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
반응형

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

 

25545번: MMST

첫째 줄에 그래프의 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(1 \leq N \leq 200\,000$, $N-1 \leq M \leq 500\,000)$ 둘째 줄부터 $M$줄에 걸쳐 $i$번째 간선의 정보가 $(U_i, V_i, C_i)$와 같이 주어진다. 이는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N > M 인 경우에는 스패닝 트리가 최대 하나밖에 나오지 않기 때문에 해당 경우에는 MMST가 나올 수 없습니다.

 

2. N <= M 인 경우에는 모든 간선의 길이가 다르기 때문에 스패닝 트리가 최소 3개가 있고  그렇기 때문에 MMST가 최소 1개 있습니다.

 

3. MST를 만들고 거기에 포함되지 않은 간선이 포함된 스패닝 트리는 무조건 MMST 가 되므로 이를 활용하여 MMST를 구합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct edge {
    int num;
    int from;
    int to;
    int dist;
};
 
bool Greater(edge left, edge right)
{
    return left.dist < right.dist;
}
 
bool Less(edge left, edge right)
{
    return left.dist > right.dist;
}
 
int N, M;
edge Edge[500000];
vector<int> ans;
int visited[500000];
int vect[200001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    if (N > M) {
        printf("NO");
        return 0;
    }
 
    for (int i = 0; i < M; i++) {
        int U, V, C;
        scanf("%d %d %d", &U, &V, &C);
        Edge[i] = { i + 1,U,V,C };
    }
 
    sort(Edge, Edge + M, Greater);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        const int a = Edge[i].from;
        const int b = Edge[i].to;
        const int num = Edge[i].num;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            visited[num] = 1;
        }
    }
    
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    int flag = false;
 
    for (int i = 0; i < M; i++) {
        const int num = Edge[i].num;
        if (visited[num] == 0) {
            ans.push_back(num);
            Union(Edge[i].from, Edge[i].to);
            break;
        }
    }
 
    for (int i = 0; i < M; i++) {
        const int a = Edge[i].from;
        const int b = Edge[i].to;
        const int num = Edge[i].num;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans.push_back(num);
        }
    }
 
    printf("YES\n");
    for (int num : ans) {
        printf("%d ", num);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 4195번 - 친구 네트워크 (C++)  (0) 2023.04.30
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 2513번 - 통학버스 (C++)  (0) 2023.04.27
[ 백준 ] 9370번 - 미확인 도착지 (C++)  (0) 2023.04.26
반응형

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

 

17490번: 일감호에 다리 놓기

2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 노드에서 돌을 놓아야 하는 개수를 입력받아 cost 배열에 저장합니다.

 

2. 끊긴 간선들은 isEdge 배열에 true로 저장합니다.

 

3. 끊긴 간선들을 제외하고 Union-Find를 이용하여 이어줍니다.

 

4. 이어줄 때 이어진 노드들 중 돌을 놓아야 하는 개수가 가장 적은 값으로 cost 배열을 갱신해줍니다.

 

5. 섬의 노드 번호를 0으로 두고, 모든 노드들을 0과 이어주면서 cost가 K를 넘으면 NO를 출력하고, 넘지 않으면 YES를 출력합니다.

 

6. 꼬리를 물고 이어져 있으므로 M의 값이 1보다 작거나 같으면 무조건 YES를 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
int N, M;
ll K;
int cost[1000001];
bool isEdge[1000001];
int vect[1000001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    cost[pa] = cost[pb] = min(cost[pa], cost[pb]);
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d %lld", &N, &M, &K);
 
    if (M <= 1) {
        printf("YES");
        return 0;
    }
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        scanf("%d", &cost[i]);
    }
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (a != N || b != 1) {
            if (a > b) {
                swap(a, b);
            }
        }
 
        isEdge[a] = true;
    }
 
    for (int i = 1; i <= N; i++) {
        if (!isEdge[i]) {
            if (i == N) {
                Union(1, N);
            }
            else {
                Union(i + 1, i);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (Find(i) != 0) {
            K -= cost[Find(i)];
            Union(0, i);
        }
 
        if (K < 0) {
            printf("NO");
            return 0;
        }
    }
 
    printf("YES");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1719번 - 택배 (C++)  (0) 2023.04.01
[ 백준 ] 13023번 - ABCDE (C++)  (0) 2023.03.31
[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
[ 백준 ] 1781번 - 컵라면 (C++)  (0) 2023.03.27
반응형

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

 

10723번: 판게아 1

첫 줄에는 테스트 케이스의 수 \(T\)가 정수로 주어진다. 이어서 매 테스트 케이스의 첫 줄에는 도시의 수 \(n\)과 도로가 건설된 횟수 \(m\)이 공백으로 구분되어 주어진다. 다음 \(n - 1\)줄에 태초

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, arr 배열에 저장합니다.

 

2. arr 배열을 오름차순으로 정렬합니다.

 

3. 새로운 간선을 입력받을 때마다 mst를 새로 만들어 줍니다.

 

4. 3의 과정에서 새로운 간선이 이전의 mst의 가장 긴 간선보다 길다면 mst를 다시 만들어 줄 필요가 없으므로 넘어갑니다.

 

5. 만들어지는 모든 mst를 XOR 해 ans에 저장합니다.

 

6. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
 
using namespace std;
 
struct node {
    int u, v, c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int vect[100000];
vector<node> arr;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int u, int v)
{
    int pu = Find(u);
    int pv = Find(v);
 
    vect[pv] = pu;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        arr.clear();
 
        for (int i = 1; i < n; i++) {
            int u, c;
            scanf("%d %d", &u, &c);
            arr.push_back({ i,u,c });
        }
 
        int Max = 987654321;
        ll temp = 0;
        ll ans = 0;
 
        for (int i = 0; i < m; i++) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
 
            arr.push_back({ u,v,c });
 
            if (Max > c) {
                temp = 0;
                Max = 0;
 
                for (int j = 0; j < n; j++) {
                    vect[j] = j;
                }
 
                sort(arr.begin(), arr.end(), cmp);
 
                for (auto& next : arr) {
                    const int u = next.u;
                    const int v = next.v;
                    const int c = next.c;
 
                    if (Find(u) != Find(v)) {
                        Union(u, v);
                        temp += c;
                        Max = max(Max, c);
                    }
                }
            }
            
            if (i == 0) {
                ans = temp;
            }
            else {
                ans ^= temp;
            }
        }
 
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
반응형

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

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, arr 배열에 저장합니다.

 

2. arr 배열을 내림차순으로 정렬합니다.

 

3. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 간선의 비용을  ans에 더해주고, 개수를 cnt에 저장합니다.

 

4. cnt가 N - 1이면 ans를 출력하고, 그렇지 않다면 -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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int A, B, C;
};
 
bool cmp(node left, node right)
{
    return left.C > right.C;
}
 
int N, M;
node arr[20000];
int vect[1001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int A, int B)
{
    int pA = Find(A);
    int pB = Find(B);
 
    vect[pB] = pA;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &arr[i].A, &arr[i].B, &arr[i].C);
    }
 
    sort(arr, arr + M, cmp);
 
    int ans = 0;
    int cnt = 0;
 
    for (int i = 0; i < M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int C = arr[i].C;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
            ans += C;
            cnt++;
        }
    }
 
    if (cnt != N - 1) {
        printf("-1");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 4963번 - 섬의 개 (C++)  (0) 2023.03.21
[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
반응형

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

 

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, arr 배열에 저장합니다.

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 간선의 개수를  ans에 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
int N, M;
int ans;
int vect[1001];
pair<int, int> arr[10000];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        scanf("%d %d", &N, &M);
        ans = 0;
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
        }
 
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &arr[i].first, &arr[i].second);
        }
 
        for (int i = 0; i < M; i++) {
            const int a = arr[i].first;
            const int b = arr[i].second;
 
            if (Find(a) != Find(b)) {
                Union(a, b);
                ans++;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
반응형

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

 

1833번: 고속철도 설계하기

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, 값이 음수이면 ans에 절댓값을 더해주고, 양수이면 arr 배열에 추가합니다.

 

2. arr 배열을 비용에 관하여 오름차순으로 정렬합니다.

 

3. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 비용을  ans에 더해주고, 이어진 노드들을 list에 저장합니다.

 

4. ans와 list.size()를 출력하고, 이어진 노드들을 차례대로 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
int N;
int ans;
vector<node> arr;
vector<pair<int, int>> list;
int vect[201];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int cost;
            scanf("%d", &cost);
 
            if (i < j) {
                if (cost < 0) {
                    ans += -cost;
                    Union(i, j);
                }
                else if(cost>0) {
                    arr.push_back({ i,j,cost });
                }
            }
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    for (auto& next : arr) {
        const int u = next.u;
        const int v = next.v;
        const int w = next.w;
 
        if (Find(u) != Find(v)) {
            list.push_back({ u,v });
            Union(u, v);
            ans += w;
        }
    }
 
    printf("%d %d\n", ans, (int)list.size());
 
    for (int i = 0; i < list.size(); i++) {
        printf("%d %d\n", list[i].first, list[i].second);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
반응형

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

 

18769번: 그리드 네트워크

재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받아 arr 배열에 저장합니다.

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 비용을  ans에 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
int vect[250001];
vector<node> arr;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int u, int v)
{
    int pu = Find(u);
    int pv = Find(v);
 
    vect[pv] = pu;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int R, C;
        scanf("%d %d", &R, &C);
 
        arr.clear();
 
        for (int i = 1; i <= R * C; i++) {
            vect[i] = i;
        }
 
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C - 1; j++) {
                int num;
                scanf("%d", &num);
 
                arr.push_back({ (i - 1) * C + j, (i - 1) * C + j + 1,num });
            }
        }
 
        for (int i = 1; i <= R-1; i++) {
            for (int j = 1; j <= C; j++) {
                int num;
                scanf("%d", &num);
 
                arr.push_back({ (i - 1) * C + j, i * C + j,num });
            }
        }
 
        sort(arr.begin(), arr.end(), cmp);
 
        int ans = 0;
 
        for (auto& next : arr)
        {
            const int u = next.u;
            const int v = next.v;
            const int w = next.w;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                ans += w;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12

+ Recent posts

티스토리툴바