[백준] 11438번 : LCA 2

https://bigkwangs.tistory.com/65

[백준] 11437번 : LCA

해당문제의 시간복잡도를 개선한 문제 입니다.

 

조상을 찾아가는데에 시간복잡도가 O(n)이 소요되지만 메모리제이션을 통하여 O(logn) 으로 단축하였습니다.

 

https://www.acmicpc.net/status?user_id=rhkdguskim&problem_id=11438&from_mine=1 

채점 현황

주어진 데이터가 더 커지고, 시간제한은 동일한 상황에서 조상을 찾아가는데에 시간복잡도를 최적화 할 수 있습니다.

조상을 찾아갈때에 2^n 만큼 이동하면서 찾아가면 됩니다. 2^n 만큼 이동하면서 찾아가기위해서는 다이나믹 프로그래밍의 메모리제이션을 활용하여 문제를 해결할 수 있습니다.( 단점 : 메모리 사용량 증가 )

 

메모리제이션 기법:

LOG = 21, 2^20 = 1,000,000이므로

for i in range(1, LOG):
    for j in range(1, N+1):
        dp[j][i] = dp[dp[j][i-1]][i-1]

dp[j][i] 는 j의 정점에서 2^i번 만큼 올라갔을경우의 조상을 표기한다.

예를들어 깊이가10이고, 정점의 번호가 5인경우, dp[5][0] 은 자기자신 조상이기때문에 dfs 탐색을 통하여 바로 알수 있다.

dp[5][1]을 초기화 하는데 dp[5][1] = dp[dp[5][0]][0] 으로 나타낼 수 있다. 왜나면 dp[5][0]는 자기자신의 조상노드이기 때문이다.

 

dp[5][3] = dp[dp[5][2]][2]로 나타낼수 있고 이건 자기자신보다 4칸 올라간 조상노드임을 알 수 있다.

 

 

이제 공통 조상을 구하는 로직에 대하여 알아보자면, 1) 깊이를 맞춘다. 2) 서로의 깊이를 맞춰서 올려가며 공통인 조상을 찾는다.

 

1) 깊이를 맞춘다.

- 깊이의 차이가 예를들어 7일 경우, 이진수로 표현하면 111 이다. 따라서 낮을 노드를 1,2,4를 올리면 둘의 깊이가 맞춰진다.

 

1) 공통 조상을 찾아간다.

- 공통 조상을 찾을때에는 둘의 공통 조상이 같지 않을경우 위에서부터 아래로 순회하는데 공통의 조상이 나올때까지 자기자신의 조상을 자기자신으로 변경해준다.

def lca(a,b):
    # b가 더 깊도록 설정
    if depth[a] > depth[b]: # 노드 a가 b보다 깊이가 깊으면 스위치
        a,b = b,a
    
    for i in range(LOG -1, -1, -1):
        if depth[b] - depth[a] & (1 << i): # depth가 7일때 3번 점프한다.
            b = dp[b][i]
        
    if a == b:
        return a    
            
    for i in range(LOG -1, -1 , -1):
        if dp[a][i] != dp[b][i]:
            a = dp[a][i]
            b = dp[b][i]
    
    return dp[a][0]

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e5))
LOG = 21 # 2^20 = 1,000,000
N = int(input())
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)

depth = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
dp = [[0 for _ in range(LOG)] for _ in range(N+1)]

def dfs(rootnode, cost):
    depth[rootnode] = cost
    visited[rootnode] = True
    for childnode in graph[rootnode]:
        if not visited[childnode]:
            dp[childnode][0] = rootnode # 제일 가까운 조상초기화
            dfs(childnode, cost+1)
            
                    
def lca(a,b):
    # b가 더 깊도록 설정
    if depth[a] > depth[b]: # 노드 a가 b보다 깊이가 깊으면 스위치
        a,b = b,a
    
    for i in range(LOG -1, -1, -1):
        if depth[b] - depth[a] & (1 << i): # depth가 7일때 3번 점프한다.
            b = dp[b][i]
        
    if a == b:
        return a    
            
    for i in range(LOG -1, -1 , -1):
        if dp[a][i] != dp[b][i]:
            a = dp[a][i]
            b = dp[b][i]
    
    return dp[a][0]

dfs(1,0)
for i in range(1, LOG):
    for j in range(1, N+1):
        dp[j][i] = dp[dp[j][i-1]][i-1]
    
M = int(input())

for _ in range(M):
    a, b = map(int, input().split())
    print(lca(a,b))