백준 - LCA (11437)

let N = Int(readLine()!)!
var tree: [[Int]] = Array(repeating: [], count: N+1)
var parent = Array(repeating: 0, count: N+1)

// 인접 리스트 만들기
for _ in 0..<N-1 {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    tree[input[0]].append(input[1])
    tree[input[1]].append(input[0])
}

// 깊이 구하기
var depth = Array(repeating: 0, count: N+1)
var visited = Array(repeating: false, count: N+1)

dfs(1, 0)

func dfs(_ node: Int, _ nowDepth: Int) {
    visited[node] = true
    depth[node] = nowDepth
    for next in tree[node] {
        if !visited[next] {
            parent[next] = node
            dfs(next, nowDepth + 1)
        }
    }
}

// 질의 수행
let M = Int(readLine()!)!

for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    var (a, b) = (input[0], input[1])
    if depth[a] > depth[b] {
        (a, b) = (b, a)
    }
    
    while depth[a] != depth[b] { // 길이 맞추기
        b = parent[b]
    }
    
    // 최소 공통 조상 노드 찾기
    while a != b {
        a = parent[a]
        b = parent[b]
    }
    
    print(a)
}

주어진 데이터의 크기가 크지 않아 일반적인 LCA 알고리즘으로 풀 수 있다.

풀이 과정

1. 트리의 인접 리스트를 구현한다.
2. DFS를 사용해서 각 노드의 부모 노드와 깊이 값을 저장한다.
3. 각 질의를 수행한다. 두 노드의 깊이를 먼저 똑같이 맞춰준 다음 부모 노드로 하나씩 올라가면서 최소 공통 조상 노드를 찾는다.