반응형

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

 

17398번: 통신망 분할

첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q 

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

 

2. vect[ i ] = i, cnt[ i ] = 1 로 초기화합니다.

 

3. 끊을 연결들을 stack에 저장합니다.

 

4. 끊을 연결들을 제외하고 나머지 연결들을 Union-Find를 이용하여 연결해 줍니다.

 

5. 끊을 연결들을 stack에서 하나씩 빼서 연결해 주면서 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
#include<iostream>
#include<stack>
#define ll long long
 
using namespace std;
 
int N, M, Q;
int visited[100001];
int vect[100001];
ll cnt[100001];
pair<int, int> arr[100001];
stack<int> edge;
 
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;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &Q);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int i = 0; i < Q; i++) {
        int A;
        scanf("%d", &A);
        edge.push(A - 1);
        visited[A - 1] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        if (visited[i] != 1) {
            if (Find(arr[i].first) != Find(arr[i].second)) {
                Union(arr[i].first, arr[i].second);
            }
        }
    }
 
    ll ans = 0;
 
    while(!edge.empty()){
        int a = arr[edge.top()].first;
        int b = arr[edge.top()].second;
        edge.pop();
 
        if (Find(a) != Find(b)) {
            ans += (cnt[Find(a)] * cnt[Find(b)]);
            Union(a, b);
        }
    }
 
    printf("%lld\n", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11962번 - Counting Haybales (C++)  (0) 2023.06.08
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
반응형

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

 

16168번: 퍼레이드

첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. 퍼레이드 이동이 가능한 경우는 한 붓 그리기가 가능한 경우이므로 한 붓 그리기가 가능한 지 그래프를 그려 판단합니다.

 

4. 연결된 간선의 수가 홀수인 노드의 개수가 0개 또는 2개일 경우에만 한 붓 그리기가 가능하므로 해당 조건을 만족하는 경우 모든 노드가 연결되어 있다면 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
#include<iostream>
#include<vector>
 
using namespace std;
 
int V, E;
int vect[3001];
vector<int> list[3001];
 
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", &V, &E);
 
    for (int i = 1; i <= V; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < E; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        list[a].push_back(b);
        list[b].push_back(a);
 
        if (Find(a) != Find(b)) {
            Union(a, b);
        }
    }
 
    int cnt = 0;
    int temp = Find(1);
 
    if (list[1].size() % 2 == 1) cnt++;
 
    for (int i = 2; i <= V; i++) {
        if (list[i].size() % 2 == 1) cnt++;
 
        if (cnt > 2 || temp != Find(i)) {
            printf("NO");
            return 0;
        }
    }
 
    printf("YES");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
반응형

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

 

12893번: 적의 적

첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. enemy 배열을 만들어 최초의 적을 저장해 줍니다.

 

4. Union-Find를 이용하여 각 노드의 적들을 연결해 줍니다.

 

5. 이때 서로 같은 그룹에 속해 있다면 이론은 틀린 것이므로 0을 출력하고, 그렇지 않다면 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
#include<iostream>
 
using namespace std;
 
int N, M;
int vect[2001];
int enemy[2001];
 
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++) {
        int A, B;
        scanf("%d %d", &A, &B);
 
        if (Find(A) == Find(B)) {
            printf("0");
            return 0;
        }
 
        if (enemy[A] == 0) {
            enemy[A] = B;
        }
        else {
            Union(Find(enemy[A]), B);
        }
 
        if (enemy[B] == 0) {
            enemy[B] = A;
        }
        else {
            Union(Find(enemy[B]), A);
        }
    }
 
    printf("1");
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
반응형

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

 

15789번: CTP 왕국은 한솔 왕국을 이길 수 있을까?

입력의 첫째 줄에 왕국의 수 N(3 ≤ N ≤ 100,000)과 동맹 관계의 수 M(1 ≤ M ≤ 200,000)이 주어진다. 이 후 M개의 줄에 X,Y가 주어진다. 이는 X 왕국과 Y 왕국이 동맹이라는 뜻이다. 입력의 마지막 줄에 CT

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 왕국을 이어주고, 이을 때마다 power 배열에 값을 경신해 줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 CTP 왕국이나 한솔 왕국에 속하지 않은 왕국들의 동맹국들의 수를 ans 배열에 저장합니다.

 

5. ans 배열을 내림차순으로 정렬하고, K개까지 동맹국을 더해줍니다.

 

6. 그 결과를 출력합니다.

 

[ 소스코드 ]

 

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<algorithm>
 
using namespace std;
 
int N, M;
int vect[100001];
int power[100001];
int visited[100001];
vector<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;
    power[pa] += power[pb];
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        power[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        int X, Y;
        scanf("%d %d", &X, &Y);
 
        if (Find(X) != Find(Y)) {
            Union(X, Y);
        }
    }
 
    int C, H, K;
    scanf("%d %d %d", &C, &H, &K);
    int cnt = 0;
 
    if (K) {
        for (int i = 1; i <= N; i++) {
            int temp = Find(i);
            if ((Find(C) != temp) && (temp != Find(H))) {
                if (visited[temp] == 0) {
                    visited[temp] = 1;
                    ans.push_back({ power[temp] });
                }
            }
        }
    }
 
    sort(ans.begin(), ans.end(), greater<>());
 
    int temp = power[Find(C)];
 
    for (int i = 0; i < min((int)ans.size(), K); i++) {
        temp += ans[i];
    }
    printf("%d", temp);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
반응형

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

 

17022번: Sleepy Cow Sorting

The first line of input contains $N$. The second line contains $N$ space-separated integers: $p_1, p_2, p_3, \dots, p_N$, indicating the starting order of the cows.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. N - 1부터 1까지 for문을 통해 돌면서 arr[ i ] < arr[ i - 1 ] 일 때의 i를 pivot으로 설정합니다.

 

2. pivot 부터 N - 1까지는 오름차순으로 정렬되어 있으므로 0부터 pivot - 1 까지의 수만 옮겨주면 됩니다.

 

3. 0부터 pivot - 1까지 for문을 통해 돌면서 pivot ~ N 까지의 수 중 현재 수보다 작은 수들의 개수와 현재 수 ~ pivot 사이의 수들의 개수를 더하면 원하는 수를 얻을 수 있습니다.

 

4. pivot을 출력하고, 앞의 수들의 이동 횟수를 출력합니다.

 

[ 소스코드 ]

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;
 
int N;
int arr[100000];
int segTree[200002];
int pivot;
 
void updateTree(int idx)
{
    while (idx != 0) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int l, int r)
{
    int ret = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            r--;
        }
        l >>= 1;
        r >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    for (int i = N - 1; i > 0; i--) {
        if (arr[i] < arr[i - 1]) {
            pivot = i;
            break;
        }
    }
 
    for (int i = pivot; i < N; i++) {
        updateTree(N + arr[i] - 1);
    }
 
    printf("%d\n", pivot);
    for (int i = 0; i < pivot; i++) {
        printf("%d ", pivot - i - 1 + getTree(N, N + arr[i] - 1));
        updateTree(N + arr[i] - 1);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12893번 - 적의 적 (C++)  (0) 2023.06.04
[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
반응형

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

 

14595번: 동방 프로젝트 (Large)

첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. x와 y의 부모노드가 다르다면 y부터 x까지 for문을 통해 돌면서 x와 y사이에 있는 모든 동방들을 x와 이어줍니다. 이때, j = Find( j ) 를 통해 j를 갱신해 줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 부모노드가 다르면 ans++를 해줍니다.

 

5. 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
#include<iostream>
 
using namespace std;
 
int N, M;
int vect[1000001];
int visited[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);
 
    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++) {
        int x, y;
 
        scanf("%d %d", &x, &y);
 
        if (Find(x) != Find(y)) {
            for (int j = y; j > x; j--) {
                j = Find(j);
                Union(x, j);
            }
        }
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N; i++) {
        if (visited[Find(i)] == 0) {
            visited[Find(i)] = 1;
            ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (C++)  (0) 2023.06.03
[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
반응형

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

 

20955번: 민서의 응급 수술

민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 뉴런을 이어주고, 이미 이어져 있다면 ans++를 해줍니다.

 

4. for문을 통해 1부터 N까지 돌면서 부모노드가 다르면 ans++를 해줍니다.

 

5. 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
#include<iostream>
 
using namespace std;
 
int N, M;
int vect[100001];
int ans;
int visited[100001];
 
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++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (Find(a) != Find(b)) {
            Union(a, b);
        }
        else {
            ans++;
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (visited[Find(i)] == 0) {
            visited[Find(i)] = 1;
            ans++;
        }
    }
 
    printf("%d", ans - 1);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17022번 - Sleepy Cow Sorting (C++)  (0) 2023.06.02
[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
반응형

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

 

7511번: 소셜 네트워킹 어플리케이션

각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 친구 관계를 이어주고, 부모 노드의 값이 같다면 1, 아니라면 0을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int n, k, m;
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);
 
    vect[pb] = pa;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 1; t <= T; t++) {
        scanf("%d", &n);
 
        for (int i = 1; i <= n; i++) {
            vect[i] = i;
        }
 
        scanf("%d", &k);
 
        for (int i = 0; i < k; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            Union(a, b);
        }
 
        scanf("%d", &m);
 
        printf("Scenario %d:\n", t);
 
        for (int i = 0; i < m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            if (Find(a) != Find(b)) {
                printf("0\n");
            }
            else {
                printf("1\n");
            }
        }
 
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
반응형

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

 

17352번: 여러분의 다리가 되어 드리겠습니다!

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다. 어제까지는 그랬다. "왜 다리

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 다리를 이어주고, 부모 노드의 값이 1과 다른 다리를 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
#include<iostream>
 
using namespace std;
 
int N;
int vect[300001];
 
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 = 0; i < N - 2; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (Find(a) != Find(b)) {
            Union(a, b);
        }
    }
 
    for (int i = 2; i <= N; i++) {
        if (Find(1) != Find(i)) {
            printf("1 %d", i);
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
반응형

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

 

12899번: 데이터 구조

첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 쿼리 업데이트를 통해 해당 자연수 노드에 1을 더해주고, 구간 합을 세그먼트 트리를 이용하여 구현해 줍니다.

 

2. 왼쪽 노드의 값이 원하는 인덱스의 값보다 크다면 왼쪽 노드로 들어가고, 그렇지 않다면 인덱스의 값에 왼쪽 노드의 값을 뺀 값을 이용하여 오른쪽 노드로 들어가 줍니다.

 

3. 원하는 인덱스의 노드 번호를 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int segTree[4200000];
 
void updateTree(int node, int s, int e, int idx)
{
    if (idx < s || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
void getTree(int node, int s, int e, int idx)
{
    if (s == e) {
        printf("%d\n", s);
        segTree[node]--;
        return;
    }
 
    int m = (s + e) / 2;
 
    if (segTree[node * 2] >= idx) {
        getTree(node * 2, s, m, idx);
        segTree[node]--;
    }
    else {
        getTree(node * 2 + 1, m + 1, e, idx - segTree[node*2]);
        segTree[node]--;
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int cmd, X;
        scanf("%d %d", &cmd, &X);
 
        if (cmd == 1) {
            updateTree(1, 1, 2000000, X);
        }
        else {
            getTree(1, 1, 2000000, X);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25

+ Recent posts

티스토리툴바