074 LCA (미해결)

첫번째 코드

 

최소 공통 조상 관련된 문제로 코드는 책을 참고했다.

개념이나 그림으로 이해하면 이해는 편한데 사실 코드상에서 이해가 너무 어려웠다...

사실 지금도 제대로 이해하고 있는지는 의문이다... ㅋㅋ;

 

그치만 개념은 이해가 되었기 때문에 차근차근 다음에도 풀어보면 이해할 수 있을 것이다.

 

import sys
from collections import deque
input = sys.stdin.readline
print = sys.stdout.write

n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(0, n-1):
    s, e = map(int, input().split())
    tree[s].append(e)
    tree[e].append(s)

depth = [0] * (n+1)
parent = [0] * (n+1)
visited = [False] * (n+1)

def BFS(node):
    queue = deque()
    queue.append(node)
    visited[node] = True
    level = 1
    now_size = 1
    count = 0
    while queue:
        now_node = queue.popleft()
        for next in tree[now_node]:
            if not visited[next]:
                visited[next] = True
                queue.append(next)
                parent[next] = now_node
                depth[next] = level
        count += 1
        if count == now_size:
            count = 0
            now_size = len(queue)
            level += 1

BFS(1)

def executeLCA(a, b):
    if depth[a] < depth[b]:
        temp = a
        a = b
        b = temp
    
    while depth[a] != depth[b]:
        a = parent[a]
    
    while a != b:
        a = parent[a]
        b = parent[b]
    
    return a

m = int(input())

for _ in range(m):
    a, b = map(int, input().split())
    print(str(executeLCA(a, b)))
    print('\n')

 

시간초과

---

링크