반응형

 

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

티스토리툴바