(Python/🥇3)백준알고리즘 11437번: LCA

문제 바로가기 

 

LCA

문제:

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력:

 

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

출력:

 

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

 

import sys
sys.setrecursionlimit(100000)
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


N = int(sys.stdin.readline()) # 16
graph = [[] for _ in range(N+1)]


# 양방향 노드 설정
for i in range(N-1):
    x, y = map(int, sys.stdin.readline().rstrip().split(" "))
    graph[x].append(y)
    graph[y].append(x)

parent = [0] * (N + 1)      # 각 노드의 부모 노드 정보
depth = [0] * (N + 1)       # 각 노드까지의 깊이
visited = [0] * (N + 1)     # 방문 여부
def dfs(x, idx):
    visited[x] = 1 # 방문처리해주고
    depth[x] = idx # 방문했으니 현재위치의 depth를 idx로 해줌 기본은 0
    for node in graph[x]: # 그 다음 방문위치
        if visited[node] == 1: # 이미 방문했으면
            continue # 넘어가고
        parent[node] = x # 그렇지 않으면 자식들이니깐 자식들의 부모는 내가 됨
        dfs(node, idx + 1) # 깊이탐색출발 깊이는 1 늘림
dfs(1,0)

def find_parent(left, right):

    # 깊이를 맞춰줌
    while depth[left] != depth[right]: # 깊이가 다르다.
        if depth[left] > depth[right]: # 왼쪽이 더 깊으면
            left = parent[left] # 깊이가 맞을때까지 부모로 올라옴
        else:
            right = parent[right] # 반대도 동일
    # 노드 맞추기
    while left != right: # 노드가 다르면
        left = parent[left] # 노드의 부모로 올라옴
        right = parent[right] # 노드의 부모로 올라옴
    # 주의할점 4의 조상이 2 일때 2와 4 의 공통부모는 2이다. 2는 자기자신이 부모인것이다.
    
    return left # 맞으면 리턴

# 문제 출력
m = int(sys.stdin.readline())

for i in range(m):
    left, right = map(int,sys.stdin.readline().split(" "))
    print(find_parent(left,right))

 

처음에 left, right 를 가져올 때 parent를 만들어서 맞춰주려고 했는데 메모리땜에 안될거 같다.