Algorithm/BOJ
[BOJ] - 11437번
Dortmoot
2022. 9. 15. 00:46
문제
[BOJ] - 11437번
https://www.acmicpc.net/problem/11437
11437번: LCA
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
문제 이해
더보기
문제
N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.
입력
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.
출력
M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.
예제 입력 1
15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15
예제 출력 1
2
4
2
1
3
1
- 노드 A,B가 주어졌을 때 가장 빠르게 접근 할 수 있는 공통 조상을 구하면 된다.
알고리즘
1. 시작 노드(root)로 부터 각 Node의 Depth를 구하기 위한 DFS
2. 각 노드들의 Parent 노드 설정
3. 노드 A,B 에 대해서 같은 레벨을 맞추어 준다.
4. 부모 노드를 탐색하면서 동일할 때 까지 탐색
코드
#BOJ 11437번
import sys
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline
answer = []
n = int(input())
graphs = [[] for _ in range(n+1)]
depth = [0] * (n+1)
parent = [0] * (n+1)
visited = [0] * (n+1)
for _ in range(n-1) :
start,end = map(int,input().split() )
graphs[start].append(end)
graphs[end].append(start)
# depth and parent set
def dfs(start,level):
visited[start]=1
depth[start]=level
for move in graphs[start]:
if not visited[move] :
parent[move]=start
visited[move]=1
depth[move]=level+1
dfs(move,level+1)
dfs(1,0)
def lca(a,b):
# level을 맞추어 준다.
while depth[a] != depth[b]:
if depth[a]<depth[b]:
b=parent[b]
else:
a=parent[a]
# 상위 Node 탐색
while a!=b:
a , b = parent[a] , parent[b]
return a
m = int(input())
for _ in range(m) :
a,b = map(int,input().split())
answer.append( lca(a,b) )
print( *answer)