[백준 11437번] LCA (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
graph = {i:[] for i in range(1,N+1)}

for i in range(N-1):
  x1,x2 = map(int,input().split())
  graph[x1].append(x2)
  graph[x2].append(x1)

parent = {}
check = {i:0 for i in range(1,N+1)}
depth = {i:0 for i in range(1,N+1)}

check[1] = 1
dq = deque()
dq.append((1,0))
while dq:
  x,d = dq.pop()
  depth[x] = d
  for child in graph[x]:
    if check[child]:
      continue
    check[child] = 1
    parent[child] = x
    dq.append((child,d+1))

M = int(input())
for i in range(M):
  x1,x2 = map(int,input().split())
  d1,d2 = depth[x1],depth[x2]
  if d1>d2:
    for i in range(d1-d2):
      x1 = parent[x1]
  if d1<d2:
    for i in range(d2-d1):
      x2 = parent[x2]
  for i in range(min(d1,d2)+1):
    if x1 == x2:
      print(x1)
      break
    x1 = parent[x1]
    x2 = parent[x2]

 

LCA 2 문제가 있길래 연습삼아 먼저 풀어봤다.

 

알고리즘은 간단하게 요약하면

1. 루트가 1번이므로, 1번을 기준으로 BFS로 트리를 작성한다.

2. 이때 부모가 누구인지 뿐만 아니라 깊이도 작성한다.

3. 두 노드에 대해서 깊이가 다르면 같은 층까지 일단 올라온다.

4. 한 층씩 올라오면서 같으면 출력한다.

 

LCS2 를 풀려면 빨리 통과를 해야할텐데, 내 LCA 1을 기준으로도 시간이 오래걸려서 좀 더 수정이 필요할 것 같다.

아마 경로압축 같은걸 신경써야하지 않을까 싶은데 좀 더 고민해봐야겠다.

 

 

오늘의 교훈) 시간을 좀 더 단축시켜서 LCA2를 풀어보자