반응형
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 |
