반응형

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 섬을 입력받습니다.

 

2. 2중 for문을 통해 그림을 탐색하면서 1이면 bfs를 통해 이어진 섬을 모두 0으로 바꿔주고, cnt에 1을 더해줍니다.

 

3. cnt를 출력합니다.

 

[ 소스코드 ]

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>
#include<queue>
 
using namespace std;
 
int arr[50][50];
int dy[8] = { 0,0,-1,1,-1,-1,1,1 };
int dx[8] = { -1,1,0,0,-1,1,1,-1 };
int w, h;
 
void bfs(int y, int x)
{
    queue<pair<int, int>> q;
    q.push({ y,x });
    arr[y][x] = 0;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
 
            if (yy >= 0 && yy < h && xx >= 0 && xx < w) {
                if (arr[yy][xx] == 1) {
                    arr[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    while (1) {
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) return 0;
 
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        int cnt = 0;
 
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (arr[i][j] == 1) {
                    bfs(i, j);
                    cnt++;
                }
            }
        }
 
        printf("%d\n", cnt);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21940번 - 가운데에서 만나기 (C++)  (0) 2023.03.23
[ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++)  (0) 2023.03.22
[ 백준 ] 10723번 - 판게아 1 (C++)  (0) 2023.03.20
[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
반응형

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/1926

 

1926번: 그림

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 그림을 입력받습니다.

 

2. 2중 for문을 통해 그림을 탐색하면서 1이면 bfs를 통해 그림의 크기 중 가장 큰 그림을 ans에 저장하고, cnt++를 해줍니다.

 

3. cnt와 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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
int arr[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int bfs(int y, int x)
{
    int ret = 1;
 
    queue<pair<int, int>> q;
 
    q.push({ y,x });
    arr[y][x] = 0;
 
    while (!q.empty()) {
        const int y = q.front().first;
        const int x = q.front().second;
        q.pop();
 
        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 < M) {
                if (arr[yy][xx] == 1) {
                    arr[yy][xx] = 0;
                    q.push({ yy,xx });
                    ret++;
                }
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    int ans = 0;
    int cnt = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 1) {
                ans = max(ans,bfs(i, j));
                cnt++;
            }
        }
    }
 
    printf("%d\n%d", cnt, ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1833번 - 고속철도 설계하기 (C++)  (0) 2023.03.17
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
반응형

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
반응형

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

 

9344번: 도로

어떤 나라에는 1부터 N까지 이름 붙여진 N개의 도시가 있다. 한 엔지니어는 모든 도시를 연결하는 도로를 건설하고자 한다. 즉, 모든 도시에 대해 항상 다른 어떤 도시로든 이동할 수 있어야 한다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, map 자료 구조에 이어진 노드들을 저장합니다.

 

3. p 노드와 q 노드가 연결되어 있다면 YES를 출력하고, 아니라면 NO를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<map>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
node arr[20000];
int vect[10001];
map<pair<int, int>, bool> visited;
 
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++) {
        int N, M, p, q;
        scanf("%d %d %d %d", &N, &M, &p, &q);
 
        //visited.clear();
 
        for (int i = 1; i <= N; i++) {
            vect[i] = i;
        }
 
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &arr[i].u, &arr[i].v, &arr[i].w);
        }
 
        sort(arr, arr + M, cmp);
 
        for (int i = 0; i < M; i++) {
            const int u = arr[i].u;
            const int v = arr[i].v;
            const int w = arr[i].w;
 
            if (Find(u) != Find(v)) {
                Union(u, v);
                visited[{u, v}] = true;
            }
        }
 
        if (visited[{p, q}] || visited[{q, p}]) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
반응형

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

 

1414번: 불우이웃돕기

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받아 arr 배열에 저장하고, ans에 모든 랜선의 길이를 더해줍니다.

 

2. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, ans에서 그 길이를 빼줍니다.

 

3. 연결된 간선의 길이가 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
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct node {
    int a, b, c;
};
 
bool cmp(node left, node right)
{
    return left.c < right.c;
}
 
int N;
vector<node> arr;
int vect[51];
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", &N);
 
    for (int i = 1; i <= N; i++) {
        char temp[55];
        scanf("%s", temp);
        for (int j = 1; j <= N; j++) {
            if (temp[j - 1] >= 'a' && temp[j - 1] <= 'z') {
                arr.push_back({ i,j, temp[j - 1] - 'a' + 1 });
                ans += temp[j - 1] - 'a' + 1;
            }
            else if (temp[j - 1] >= 'A' && temp[j - 1] <= 'Z') {
                arr.push_back({ i,j,temp[j - 1] - 'A' + 27 });
                ans += temp[j - 1] - 'A' + 27;
            }
        }
 
        vect[i] = i;
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    int cnt = 0;
 
    for (auto& next : arr) {
        const int a = next.a;
        const int b = next.b;
        const int c = next.c;
 
        if (Find(a) != Find(b)) {
            Union(a, b);
            ans -= c;
            cnt++;
        }
    }
 
    if (cnt != N - 1) {
        printf("-1");
    }
    else {
        printf("%d", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
반응형

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

 

14950번: 정복자

서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. 총 M번 for문을 돌면서 MST를 만들고, 간선을 이어줄 때마다 ans에 비용과 t를 더해줍니다.

 

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
#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, t;
node arr[30001];
int vect[10001];
 
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 %d", &N, &M, &t);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        scanf("%d %d %d", &arr[i].A, &arr[i].B, &arr[i].C);
    }
 
    sort(arr, arr + M, cmp);
 
    long long ans = 0;
    int temp = 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;
            ans += temp;
            temp += t;
        }
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14
[ 백준 ] 1414번 - 불우이웃돕기 (C++)  (0) 2023.03.13
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09

+ Recent posts

티스토리툴바