Loading [MathJax]/jax/output/CommonHTML/jax.js
반응형

 

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)이 걸리게 되므로 효율적이지 않습니다.

 

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

 

첫 번째 코드는 같은 깊이까지 한 칸씩 올라가는 코드이고, 두 번째 코드는 2i칸씩 올라가는 코드입니다.

 

[ 소스 코드 ]

 

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

티스토리툴바