백준 - LCA 11437 (Python)

[Gold III] LCA - 11437
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개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

 

 

예제입력 / 예제출력

문제이해 및 코드설명

그래프를 활용하여 트리구조의 최소 공통조상을 찾는 문제이다. 처음에 너무 막막하고 어디서 부터 시작해야할지 몰라  다른사람들의 코드를 보며 이해에 초점을 둔 문제이다.

우선 부모 노드에 대한 정보, 각 노드까지깊이, 깊이계산여부를 초기값으로 정하고 그래프를 입력받는다.

이후 루트노드부터 모든 정점의 깊이를 구하는 함수를 작성하며, 재귀적으로 코드를 실행하며 모든 코드에 적용되도록한다. A,B 최소 공통을 찾는 함수 Ica를 작성해준다. 루트노드부터 시작하는 함수를 초기에 실행해서 모든 정점의 깊이를 입력한 후 a,b 값을 입력받아 2 정점의 최소공통조상을 구하면 된다.

문제를 풀며, 어렵고 낯설었지만 이런 형태의 문제를 많이풀어보며 풀이과정 및 생각하는 순서를 정리해야겠다고 

생각이 들었다.

 

코드

import sys
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정

n = int(input())

# 초기값 세팅 
parent = [0] * (n + 1) # 부모 노드 정보
d = [0] * (n + 1) # 각 노드까지의 깊이
c = [0] * (n + 1) # 각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n + 1)] # 그래프(graph) 정보

# 그래프에 값 넣기
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
def dfs(x, depth):
    c[x] = True # 깊이 계산 여부
    d[x] = depth # 매번 노드에 대해 깊이값을 기록
    for y in graph[x]: # 인접 노드의 깊이값 검사 (노드 1부터 시작)
        if c[y]: # 이미 깊이를 구했다면 넘기기
            continue
        parent[y] = x # 부모노드를 루트노드인 1로 바꾸고 
        dfs(y, depth + 1) # 현재까지의 노드 깊이에 +1 

# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
    # 먼저 깊이(depth)가 동일하도록
    while d[a] != d[b]: # 두 노드의 깊이가 같을 때까지
        if d[a] > d[b]: # 깊이가 더 깊은 노드는 
            a = parent[a] # 자신의 부모노드가 되어 한 단계 올라가기
        else:
            b = parent[b] 
    # 노드가 같아지도록
    while a != b: # 두 노드가 같을 때까지
        a = parent[a] # 자신의 부모노드가 되어 한 단계씩 올라가기
        b = parent[b]
    return a # 결국 하나의 노드 값이 산출 = 최소공통조상 노드

dfs(1, 0) # 루트 노드는 1번 노드

m = int(input())

for i in range(m): # m개 반복
    a, b = map(int, input().split())
    print(lca(a, b))