반응형

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

 

14268번: 회사 문화 2

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. dfs를 통해 각 노드가 몇 번에서 시작해서 몇 번에서 끝나는지 오일러 경로 테크닉을 이용하여 s[ n ], e[ n ]에 저장합니다.

 

2. 특정 인원에게 칭찬을 하면 update 함수를 통해 s[ i ]에서 e [ i ]까지 값을 업데이트해줍니다.

 

3. 해당 인원의 칭찬 값을 구하기 위해서 segment tree에서 s[ i ]번 노드의 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int n, m;
vector<int> list[100001];
int cnt;
int s[100001];
int e[100001];
int segTree[262222];
int lazy[262222];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        segTree[node] += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
 
    return;
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int diff)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node] += diff;
        if (s != e) {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, diff);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, diff);
}
 
void query(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (idx < s || idx > e) return;
 
    if (s == e) {
        printf("%d\n", segTree[node]);
        return;
    }
 
    int m = (s + e) / 2;
    query(node * 2, s, m, idx);
    query(node * 2 + 1, m + 1, e, idx);
}
 
void dfs(int num)
{
    s[num] = ++cnt;
 
    for (int next : list[num]) {
        dfs(next);
    }
 
    e[num] = cnt;
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        int parent;
        scanf("%d", &parent);
 
        if (parent != -1) {
            list[parent].push_back(i);
        }
    }
 
    dfs(1);
 
    for (int j = 0; j < m; j++) {
        int com, i;
        scanf("%d %d", &com, &i);
 
        if (com == 1) {
            int w;
            scanf("%d", &w);
 
            updateTree(1, 1, n, s[i], e[i], w);
        }
        else {
            query(1, 1, n, s[i]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
반응형

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

 

14267번: 회사 문화 1

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. vector<int> arr[ n ]을 만들고, 직속 후배들을 저장합니다.

 

2. dfs를 활용하여 직속 상사들의 칭찬값들을 모두 더해 후배의 칭찬값에 적용시킵니다.

 

3. 1부터 n까지 칭찬값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
vector<int> arr[100001];
int good[100001];
int ans[100001];
int n, m;
 
void dfs(int num, int w)
{
    if (num == 0) return;
 
    ans[num] = good[num] + w;
 
    for (auto& next : arr[num]) {
        dfs(next, good[num] + w);
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        int parent;
        scanf("%d", &parent);
 
        if (parent != -1) {
            arr[parent].push_back(i);
        }
    }
 
    for (int j = 0; j < m; j++) {
        int i, w;
        scanf("%d %d", &i, &w);
 
        good[i] += w;
    }
 
    dfs(1, 0);
 
    for (int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
반응형

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

 

1240번: 노드사이의 거리

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 연결된 노드와 거리를 입력받고, vector<pair<int, int>> list[ 1001 ]에 저장합니다.

 

2. visited 배열을 만들어 각 노드의 방문 여부를 기록합니다.

 

3. 거리를 알고 싶은 노드를 입력 받고, 깊이 우선 탐색을 활용하여 노드 사이의 거리를 출력합니다.

 

4. visited 배열을 초기화 합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[1001];
int visited[1001];
int a, b;
 
void dfs(int num, int dist)
{
    if (num == b) {
        printf("%d\n", dist);
        return;
    }
    for (auto& next : list[num]) {
        if (visited[next.first] != 1) {
            visited[next.first] = 1;
            dfs(next.first, dist + next.second);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    for (int i = 0; i < M; i++) {
        fill(visited, visited + N + 1, 0);
        scanf("%d %d", &a, &b);
        visited[a] = 1;
        dfs(a, 0);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
반응형

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

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 노드의 부모 노드를 입력받고, 부모 노드가 -1일 경우 해당 노드를 root 변수에 저장합니다.

 

2. 입력받은 부모 노드를 기준으로 vector<int> list[ 50 ] 배열에 그래프를 저장합니다.

 

3. dfs를 활용하여 지울 노드들을 방문 처리해 줍니다.

 

4. dfs를 활용하여 루트 노드부터 모든 노드를 방문하면서 자식 노드가 없는 노드들의 개수를 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>
#include<vector>
 
using namespace std;
 
int N;
vector<int> list[50];
int visited[50];
int ans;
int root;
 
void dfs(int num)
{
    int temp = 0;
    if (visited[num]) return;
    visited[num] = 1;
 
    for (auto& next : list[num]) {
        if (visited[next] != 1) {
            dfs(next);
            temp++;
        }
    }
 
    if (temp == 0) ans++;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int num;
        scanf("%d", &num);
        if (num != -1) {
            list[num].push_back(i);
        }
        else {
            root = i;
        }
    }
 
    int del;
    scanf("%d", &del);
 
    dfs(del);
 
    ans = 0;
 
    dfs(root);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1240번 - 노드사이의 거리 (C++)  (0) 2023.03.10
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07
[ 백준 ] 21924번 - 도시 건설 (C++)  (0) 2023.03.06
반응형

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

 

3584번: 가장 가까운 공통 조상

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 읽어 보고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/95

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까지

rudalsd.tistory.com

 

1. 입력받은 트리를 통해서 루트를 level 1, 이후 자식으로 넘어갈 때마다 level을 1씩 늘려나가면서 각 노드의 level을 저장합니다.

 

2. arr[ N ][ i ]에서 N은 노드의 번호, i는 $2^{i}$번 째 부모를 나타냅니다.

 

3. 입력받은 두 수의 level을 맞춰줍니다.

 

4. 만약 두 수가 같지 않다면 두 수가 같을 때까지 level을 낮춰줍니다.

 

5. 마지막에 그 수를 출력합니다.

 

[ 소스코드 ]

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
107
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
 
using namespace std;
 
int N;
int arr[10001][14];
int level[10001];
vector<int> list[10001];
 
void dfs(int num, int lv) {
    level[num] = lv;
    for (auto next : list[num]) {
        dfs(next, lv + 1);
    }
}
 
int find(int A, int B) {
    int ret = 0;
 
    if (level[A] > level[B]) {
        int temp = A;
        A = B;
        B = temp;
    }
 
    int size = ceil(log2(N));
 
    if (level[A] != level[B]) {
        for (int i = size - 1; i >= 0; i--) {
            int next = arr[B][i];
            if (next == 0) continue;
            if (level[A] < level[next]) {
                B = next;
            }
        }
 
        B = arr[B][0];
    }
    
    if (A != B) {
        for (int i = size - 1; i >= 0; i--) {
            int pa = arr[A][i];
            int pb = arr[B][i];
 
            if (pa != pb) {
                A = pa;
                B = pb;
            }
        }
 
        A = arr[A][0];
    }
 
    return A;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        scanf("%d", &N);
 
        int size = ceil(log2(N));
        
        memset(arr, 0, sizeof(arr));
        
        for (int i = 1; i <= N; i++) {
            list[i].clear();
        }
 
        for (int i = 0; i < N - 1; i++) {
            int A, B;
            scanf("%d %d", &A, &B);
 
            arr[B][0] = A;
            list[A].push_back(B);
        }
 
        int root = 0;
 
        for (int i = 1; i <= N; i++) {
            if (arr[i][0] == 0) {
                root = i;
                break;
            }
        }
 
        dfs(root, 1);
 
        for (int i = 1; i < size; i++) {    //희소 배열
            for (int j = 1; j <= N; j++) {
                int next = arr[j][i - 1];
                arr[j][i] = arr[next][i - 1];
            }
        }
 
        int A, B;
        scanf("%d %d", &A, &B);
 
        printf("%d\n", find(A, B));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1774번 - 우주신과의 교감 (C++)  (0) 2022.11.20
[ 백준 ] 10282번 - 해킹 (C++)  (0) 2022.11.19
[ 백준 ] 5529번 - 저택 (C++)  (0) 2022.11.17
[ 백준 ] 16933번 - 벽 부수고 이동하기 3 (C++)  (0) 2022.11.16
[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15
반응형

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

 

15681번: 트리와 쿼리

트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 루트를 기준으로 재귀 함수를 통해 자식 노드들의 개수를 dp 배열에 저장합니다.

 

2. 점화식은 dp[ cur ] += dp[ next ] 입니다.

 

3. return을 할 때 자기 자신도 포함시켜야 하기 때문에 return dp[ cur ] += 1 을 해줍니다.

 

3. 마지막에 dp[num]을 하나씩 출력해주면 됩니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, R, Q;
vector<int> list[100001];
int dp[100001];
int visited[100001];
 
int dfs(int cur)
{
    if (dp[cur] != 0) return dp[cur];
    if (visited[cur] == 1) return 0;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next] != 1) {
            dp[cur] += dfs(next);
        }
    }
 
    return dp[cur] += 1;
}
 
int main()
{
    scanf("%d %d %d", &N, &R, &Q);
 
    for (int i = 1; i < N; i++) {
        int U, V;
        scanf("%d %d", &U, &V);
        list[U].push_back(V);
        list[V].push_back(U);
    }
 
    dfs(R);
 
    for (int i = 0; i < Q; i++) {
        int num;
        scanf("%d", &num);
        printf("%d\n", dp[num]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16933번 - 벽 부수고 이동하기 3 (C++)  (0) 2022.11.16
[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15
[ 백준 ] 7682번 - 틱택토 (C++)  (0) 2022.11.13
[ 백준 ] 13913번 - 숨바꼭질 4 (C++)  (0) 2022.11.12
[ 백준 ] 1976번 - 여행 가자 (C++)  (0) 2022.11.11
반응형

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

 

3176번: 도로 네트워크

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/95?category=1073064 

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까

rudalsd.tistory.com

 

1. 희소 배열의 각 노드에 max, min 값을 각각 저장해줍니다.

 

2. 두 노드의 높이를 맞춰줄 때 Max, Min을 계속 갱신해줍니다.

 

3. Min과 Max를 출력해줍니다.

 

[ 소스 코드 ]

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
107
108
109
110
111
112
113
114
115
#include<cstdio>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int to;
    int max;
    int min;
};
 
int N, K;
int H;        //트리의 높이
node arr[100001][18];
vector<vector<node>> list;
int visited[100001];
int h[100001];    //노드의 높이
 
void dfs(int cur)    //arr[cur][0] 채우기
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur])
    {
        if (visited[next.to] != 1) {
            arr[next.to][0] = { cur, next.max, next.min };
            h[next.to] = h[cur] + 1;
            dfs(next.to);
        }
    }
}
 
void makeTree()        //트리 만들기
{
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= N; j++) {
            auto next = arr[j][i - 1];
            if (arr[next.to][i-1].to != 0) {
                int Max = max(next.max, arr[next.to][i - 1].max);
                int Min = min(next.min, arr[next.to][i - 1].min);
                arr[j][i] = { arr[next.to][i - 1].to, Max, Min };
            }
        }
    }
}
 
void Dist(int a, int b)    //a, b 사이의 가장 긴 도로와 짧은 도로 길이 구하기
{
    if (h[a] > h[b]) {    //a가 트리의 더 위에 있도록
        int temp = a;
        a = b;
        b = temp;
    }
 
    int Min = 987654321;
    int Max = 0;
 
    if (h[a] != h[b]) {    //높이가 다르다면 맞춰주기
        for (int i = H; i >= 0; i--) {
            int mask = 1 << i;
            if (h[b] - h[a] >= mask) {
                Min = min(Min, arr[b][i].min);
                Max = max(Max, arr[b][i].max);
                b = arr[b][i].to;
            }
            if (h[a] == h[b]) break;
        }
    }
 
    if(a!=b) {    //같은 높이일 때 서로 다른 숫자면
        for (int i = H; i >= 0; i--) {
            if (arr[a][i].to == arr[b][i].to || arr[a][i].to == 0 || arr[b][i].to == 0) continue;
            Max = max(Max, max(arr[a][i].max,arr[b][i].max));
            Min = min(Min, min(arr[a][i].min, arr[b][i].min));
            a = arr[a][i].to;
            b = arr[b][i].to;
        }
 
        Max = max(Max, max(arr[a][0].max, arr[b][0].max));
        Min = min(Min, min(arr[a][0].min, arr[b][0].min));
    }
 
    printf("%d %d\n", Min, Max);
}
 
int main()
{
    scanf("%d", &N);
 
    H = ceil(log2(N));
    list.resize(N + 1);
    h[1] = 1;
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, dist;
        scanf("%d %d %d", &a, &b, &dist);
 
        list[a].push_back({ b,dist,dist });
        list[b].push_back({ a,dist,dist });
    }
 
    dfs(1);
    makeTree();
 
    scanf("%d", &K);
 
    for (int i = 0; i < K; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        Dist(a, b);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
반응형

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

 

11438번: LCA 2

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정

www.acmicpc.net

 

 

[ 문제풀이 ]

 

다음 글의 두 번째 풀이 방식과 동일합니다!

https://rudalsd.tistory.com/68?category=1064612 

 

[ 백준 ] 1761번 - 정점들의 거리 (C++)

https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄

rudalsd.tistory.com

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
int N, M;
vector<int> list[100001];    //간선 정보
int parent[100001][18];        //2^i번째 부모
int height[100001];            //각 노드의 높이
int visited[100001];        //방문 여부
int limit;
 
void dfs(int cur)        //그래프
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next] == 0) {
            height[next] = height[cur] + 1;
            parent[next][0] = cur;
            dfs(next);
        }
    }
}
 
int find(int a, int b)        //LCA 찾기
{
    if (height[a] > height[b]) {    //a가 루트에 더 가깝게
        int temp = a;
        a = b;
        b = temp;
    }
 
    for (int i = limit; i >= 0; i--) {    //높이 맞추기
        int mask = 1 << i;
        if (height[b] - height[a] >= mask) {
            b = parent[b][i];
        }
    }
 
    if (a == b) return a;    //같은 노드라면 a return
 
    for (int i = limit; i >= 0; i--) {        //같인 부모 찾기
        if (parent[a][i] == parent[b][i]) continue;
 
        a = parent[a][i];
        b = parent[b][i];
    }
    
    return parent[a][0];
}
 
int main()
{
    scanf("%d", &N);
 
    limit = ceil(log2(N));
 
    for (int i = 0; i < N - 1; i++) {    //간선 정보 얻기
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    dfs(1);
 
    for (int i = 1; i < limit; i++) {    //parent배열 채우기
        for (int j = 1; j <= N; j++) {
            int next = parent[j][i - 1];
            if (next != 0) {
                parent[j][i] = parent[next][i - 1];
            }
        }
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        printf("%d\n", find(a, b));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01
반응형

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

 

11725번: 트리의 부모 찾기

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

먼저 vector를 이용하여 그래프 입력을 받고, 입력받은 그래프를 바탕으로 DFS를 돌려 문제를 풀 수 있습니다. 한번 방문한 노드는 다시 방문할 필요가 없으므로 visited배열을 통해 방문 체크를 해주시면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
vector<int> list[100001];
int visited[100001];
int parent[100001];
 
void dfs(int node)
{
    if (visited[node] == 1) return;
    visited[node] = 1;
 
    for (auto next : list[node]) {
        if (visited[next] != 1) {
            parent[next] = node;
            dfs(next);
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    dfs(1);
 
    for (int i = 2; i <= N; i++) {
        printf("%d\n", parent[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01
[ 백준 ] 11444번 - 피보나치 수 6 (C++)  (0) 2022.07.30
[ 백준 ] 2243번 - 사탕상자 (C++)  (0) 2022.07.29
[ 백준 ] 5719번 - 거의 최단 경로 (C++)  (0) 2022.07.27

+ Recent posts

티스토리툴바