189. LCA
1. Python
DFS
import sys
sys.setrecursionlimit(int(1e5))
n = int(input())
parent = [0] * (n + 1) #부모 노드 정보
d = [0] * (n + 1) #각 노드 까지의 깊이
c = [0] * (n + 1) #각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
#루트 노드부터 시작하여 깊이 탐색
def dfs(x, depth):
c[x] = True
d[x] = depth
for y in graph[x]:
if c[y]:
continue
parent[y] = x
dfs(y, depth + 1)
# A와 B의 최소 공통 조상 찾기
def lca(a, b):
#깊이가 동일하도록 만들기
while d[a] != d[b]:
if d[a] > d[b]:
a = parent[a]
else:
b = parent[b]
#노드가 같아지도록
while a != b:
a = parent[a]
b = parent[b]
return a
dfs(1, 0) #루트 노드는 1번
m = int(input()) # 가장 가까운 공통 조상을 알고싶은 쌍의 개수
for i in range(m):
a, b = map(int, input().split())
print(lca(a, b))
2. C++
BFS
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N, M;
int u, v;
queue<int> q;
vector<int> node[50001];
bool check[50001];
int parent[50001];
int depth[50001];
int LCA(int u, int v)
{
// v가 u보다 더 깊은 노드로 세팅
if (depth[u] > depth[v]) swap(u, v);
// 두 노드의 깊이가 같아질때까지 v노드는 위로 거슬러 올라감
while (depth[u] != depth[v]) v = parent[v];
// 두 노드가 같아질때 까지 위로 거슬러 올라감
while (u != v)
{
u = parent[u];
v = parent[v];
}
return u; // LCA 리턴
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
// 해당노드에 연결된 노드 push
for (int i = 0; i < N-1; i++)
{
cin >> u >> v;
node[u].push_back(v);
node[v].push_back(u);
}
check[1] = true;
q.push(1); // 트리의 루트
while (!q.empty())
{
int x = q.front(); // 부모 노드
q.pop();
for (int i = 0; i < node[x].size(); i++)
{
if (!check[node[x][i]]) // 현재노드를 방문한적 없다면
{
depth[node[x][i]] = depth[x] + 1; // 깊이 +1
check[node[x][i]] = true; // 방문표시
parent[node[x][i]] = x; // 부모노드 입력
q.push(node[x][i]); // 큐에 추가
}
}
}
cin >> M;
for (int i = 0; i < M; i++)
{
cin >> u >> v;
cout << LCA(u, v) << '\n';
}
}
Author And Source
이 문제에 관하여(189. LCA), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/189.-LCA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)