[Algorithm] 가장 가까운 공통 조상

[hwangJi-dev]

💬 문제

https://www.acmicpc.net/problem/3584

💬 Idea

• 각 노드의 가장 가까운 부모 노드를 배열에 저장한다.
• 목표 노드부터 최상단 노드까지 거꾸로 탐색한 결과를 각각 도출한다. (q1, q2)
• q1, q2의 공통 원소를 찾아 필터링하고 그 중 첫번째 노드를 출력한다.

💬 풀이

import Foundation

func solution3584() {
    let t = Int(readLine()!)!
    
    for _ in 1...t {
        let n = Int(readLine()!)!
        var nodes = Array(repeating: 0, count: n + 1)
        
        for _ in 1..<n {
            let node = readLine()!.components(separatedBy: .whitespaces).map({ Int($0)! })
            nodes[node[1]] = node[0]
        }
        
        func dfs(_ start: Int) -> [Int] {
            var visitedQueue: [Int] = []
            var needToVisitNode = start
            
            while needToVisitNode != 0 {
                visitedQueue.append(needToVisitNode)
                needToVisitNode = nodes[needToVisitNode]
            }
            
            return visitedQueue
        }
        
        let tc = readLine()!.components(separatedBy: .whitespaces).map({ Int($0)! })
        
        func getCommonAncestor(_ n1: Int, _ n2: Int) -> Int {
            let queue1 = dfs(n1)
            let queue2 = dfs(n2)
            return queue1.filter({ queue2.contains($0) }).first!
        }
        
        print(getCommonAncestor(tc[0], tc[1]))
    }
}