백준 11437 - LCA

문제 링크 : https://www.acmicpc.net/problem/11437

 

문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

풀이 과정

https://readytojoin.tistory.com/entry/LCA-%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81-%EC%B0%BE%EA%B8%B0

LCA - 최소 공통 조상 찾기

기본 LCA 구현 문제이다. DFS로 depth 와 parent 를 각 노드마다 계산한 다음, a와 b의 depth 를 맞춘 뒤 a와 b가 같아질 때 까지 동시에 부모 노드로 건너간다.

 

# 11437. LCA ( GOLD 3 )
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

n = int(input().rstrip())
parent = [-1 for _ in range(n+1)]
graph = [[] for _ in range(n+1)]
depth = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
for _ in range(n-1):
  a, b = map(int, input().rstrip().split())
  graph[a].append(b)
  graph[b].append(a)

def DFS(now, p, d):
  global parent
  global graph
  global visited
  global depth
  visited[now] = 1
  depth[now] = d

  for next in graph[now]:
    if visited[next] == 0: DFS(next, now, d + 1)

  parent[now] = p

DFS(1, -1, 0)

def LCA(a, b):
  global parent
  global graph
  global visited
  global depth

  while depth[a] > depth[b]: a = parent[a]
  while depth[a] < depth[b]: b = parent[b]
  while a != b:
    a = parent[a]
    b = parent[b]
  return a

m = int(input().rstrip())
for _ in range(m):
  a, b = map(int, input().rstrip().split())
  print(LCA(a, b))