반응형

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

 

1761번: 정점들의 거리

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩

www.acmicpc.net

 

 

[ 문제풀이 ]

 

문제 풀이 과정은 다음과 같습니다.

 

1. 각각의 노드들에 대해서 연결된 에지들을 list배열에 저장합니다.

 

2. 1번 노드를 루트 노드로 설정하고, 부모는 0, 깊이는 1로 설정합니다. 

 

3. 각 노드들의 부모, 깊이, 부모 노드까지의 거리를 각각 저장합니다.

 

4. 입력받은 노드들에 대해서 높이가 같아질 때까지 올라가고 그때까지의 거리를 저장합니다.

 

5. 노드들의 깊이가 같아졌을 때 같은 노드를 가리키고 있다면 break

 

6. 다른 노드를 가리키고 있다면 계속 올라가면서 5번을 반복합니다.

 

하지만 같은 깊이까지 한칸씩 올라가면 드는 시간이 최대 O(NM)이 걸리게 되므로 효율적이지 않습니다.

 

따라서, 깊이 정보를 $2^{i}$로 저장하게 된다면 O(MlogN)의 시간으로 단축할 수 있습니다.

 

첫 번째 코드는 같은 깊이까지 한 칸씩 올라가는 코드이고, 두 번째 코드는 $2^{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
#include<iostream>        //768ms
#include<vector>
#include<queue>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
struct tree {
    int parent;
    int depth;
    int dist;
};
 
int N, M;
vector<node> list[40001];        //연결된 노드 저장
int visited[40001];
tree arr[40001];            //부모 노드, 깊이, 거리를 저장할 배열
 
int main()
{
    cin >> N;
 
    arr[1] = { 0, 1, 0 };
 
    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 });
        list[b].push_back({ a,dist });
    }
 
    queue<node> q;
    q.push({ 1, 0 });
 
    while (!q.empty())        //1번 노드의 깊이를 1로 두고 내려갈수록 깊이 +1
    {
        int to = q.front().to;
        q.pop();
 
        if (visited[to] == 1) continue;
        visited[to] = 1;
 
        for (int i = 0; i < list[to].size(); i++) {
            int next = list[to][i].to;
            int dist = list[to][i].dist;
            if (visited[next] != 1) {
                arr[next] = { to, arr[to].depth + 1, dist };
                q.push({ next, 0 });
            }
        }
    }
 
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        int a, b;
        int ans = 0;
        scanf("%d %d", &a, &b);
        if (arr[a].depth < arr[b].depth) {            //깊이가 다르다면 깊이 맞춰주기
            while (arr[a].depth != arr[b].depth) {
                ans += arr[b].dist;
                b = arr[b].parent;                
            }
        }
        else if (arr[a].depth > arr[b].depth) {
            while (arr[a].depth != arr[b].depth) {
                ans += arr[a].dist;
                a = arr[a].parent;
            }
        }
        //깊이가 같다면
        while (1) {        //부모가 같아질 때까지 올라가기
            if (a == b) {
                break;
            }
            ans += arr[a].dist + arr[b].dist;
            a = arr[a].parent;
            b = arr[b].parent;
        }
 
        printf("%d\n", ans);
    }
}
cs

 

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>            //40ms
#include<vector>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int N, M;
vector<node> list[40001];        //연결된 노드 저장
int visited[40001];
int parent[40001][16];        //parent[i][j] i번 노드의 2^i번째 부모
int dist[40001][16];        //dist[i][j] i번 노드의 2^i번째 부모까지의 거리
int depth[40001];            //노드의 깊이 배열
 
void dfs(int cur, int D)    //현재 노드와 깊이
{
    if (visited[cur]) return;
    visited[cur] = 1;
    depth[cur] = D;
 
    for (int i = 0; i < list[cur].size(); i++) {
        int next = list[cur][i].to;
        int cost = list[cur][i].dist;
        if (visited[next] == 1) continue;
        parent[next][0] = cur;
        dist[next][0] = cost;
        dfs(next, D + 1);
    }
}
 
int LCA(int start, int end)        //공통 조상 찾기
{
    if (depth[start] > depth[end]) {
        int temp = start;
        start = end;
        end = temp;
    }
 
    int ret = 0;
 
    for (int i = 15; i >= 0; i--)    //깊이를 같게 만들기
    {
        int mask = 1 << i;
 
        if (depth[end] - depth[start] >= mask)
        {
            ret += dist[end][i];
            end = parent[end][i];
        }
    }
 
    if (start == end) {    //깊이가 같을 때 같은 노드에 있다면
        return ret;
    }
 
    for (int i = 15; i >= 0; i--) {        //부모가 같다면 최초의 공통 조상이거나 넘었거나
        if (parent[start][i] == parent[end][i]) continue;
 
        ret += dist[start][i] + dist[end][i];
        start = parent[start][i];
        end = parent[end][i];
    }
 
    ret += dist[start][0] + dist[end][0];    //start, end는 부모가 같으므로 한 칸 더 올라가야함
    return ret;
}
 
int main()
{
    cin >> N;
 
    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 });
        list[b].push_back({ a,dist });
    }
 
    dfs(1, 1);
 
    for (int i = 1; i < 16; i++) {        //parent[node][i] node의 2^i번째 부모
        for (int j = 1; j <= N; j++) {
            int preParent = parent[j][i - 1];
            parent[j][i] = parent[preParent][i - 1];
 
            if (parent[j][i] == 0) continue;
 
            int preDist = dist[j][i - 1];
            dist[j][i] = preDist + dist[preParent][i - 1];
        }
    }
 
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", LCA(a, b));
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 10830번 - 행렬 제곱 (C++)  (0) 2022.07.21
[ 백준 ] 1786번 - 찾기 (C++)  (0) 2022.07.20
[ 백준 ] 1708번 - 볼록 껍질 (C++)  (0) 2022.07.17
[ 백준 ] 1086번 - 박성원 (C++)  (0) 2022.07.15
[ 백준 ] 17371번 - 이사 (C++)  (0) 2022.07.14

+ Recent posts

티스토리툴바