728x90
최소 공통조상이란?
두 노드의 조상이 처음으로 같은 경우를 최소 공통 조상이라고 한다. 지금부터 최소 공통 조상을 구하는 알고리즘을
알아보도록 하겠다.
위와 같이 트리가 하나 있다. 여기서 1이 루트라 하고 각 깊이를 구하면 다음과 같다.
여기서 노드 3과 노드 8의 최소 공통 조상은 그림과 같이 노드 2인 것을 알 수 있다.
하나 더 예시를 보자면 노드 8과 노드 10의 최소 공통 조상은 노드 10인 것을 알 수 있다.
바로 본론으로 들어가자면 최소 공통 조상 알고리즘은
1. 두 노드의 깊이를 확인한다.
2. 만약 하나가 다른 노드보다 작다면 깊이-1을 해준다.
3. 만약 깊이가 같다면 두 노드 모드 깊이 -1를 해준다.
4. 깊이-1 해주면서 만약 노드가 같아지는 지점을 찾는다.
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
|
#include <iostream>
#include <vector>
#define max 100
using namespace std;
/*
입력 값
10 노드의 갯수
9 간선의 갯수
1 2
2 3
4 5
1 4
2 6
4 7
6 9
6 10
10 8
*/
vector <int> adj[max];
bool visit[max] = {false};
int depth[max]; // 깊이를 저장
int parents[max]; // 각 노드들의 부모를 저장
int V,E;
// 노드들의 깊이와 부모를 설정해주는 DFS 함수
void DFS(int node,int dep){
visit[node] = true;
depth[node] = dep;
for(int i = 0;i<adj[node].size();i++){
int next_node = adj[node][i];
if(visit[next_node]){continue;} // 만약 방문만 정점이면 탐색x
parents[next_node] = node; // 다음노드의 부모는 현재노드가 된다. (위에서 부터 탐색하므로)
DFS(next_node,dep+1); // 다음노드와 깊이를 +1해준다.
}
}
int LCA(int node_a,int node_b){
if(node_a == node_b){return node_a;} // 만약 두 노드가 같으면 노드 반환
if(depth[node_a] == depth[node_b]){return LCA(parents[node_a],parents[node_b]);} //두 노드의 깊이가 같을 때
else if(depth[node_a]>depth[node_b]){return LCA(parents[node_a],node_b);} //만약 node_a가 더 깊이가 깊을 때
else{return LCA(node_a,parents[node_b]);} // 만약 node_b가 더 깊이가 깊을 때
}
int main(void)
{
cin >> V >> E;
// 인접 리스트 생성
for(int i = 0;i<E;i++){
int a,b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
DFS(1,0); // 1이 루트이므로 1 먼저 탐색하여 깊이를 구해준다.
cout << LCA(4,7); //노드4와 노드7의 최소 공통 조상 출력
}
|
cs |
추천문제
11437번: LCA
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
728x90
'그래프 이론' 카테고리의 다른 글
[C++알고리즘][정점들을 인접행렬, 인접 리스트로 표현하기] (0) | 2020.11.30 |
---|