공통 조상 찾기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 트리를 직접 구현하기 보다는, 현재 노드의 부모 노드를 저장하는 배열을 만들어 부모 노드를 저장한 후
• X의 부모 노드를 하나 씩 Bool 배열을 통해 체크해 나가고, Y의 부모 노드를 하나 씩 Bool 배열을 통해 체크해 나가면서
• 최초로 true인 노드가 가장 가까운 공통 조상이 되는 것을 알 수 있음

5. 전체 코드

//MARK: - 공통 조상 찾기

//MARK: - Framework
import Foundation

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    
    let n: Int = input.map { Int($0) }[0] ?? 0
    var X: Int = input.map { Int($0) }[1] ?? 0
    var Y: Int = input.map { Int($0) }[2] ?? 0
    var parent: [Int] = Array(repeating: 0, count: n + 10)
    var check: [Bool] = Array(repeating: false, count: n + 10)
    
    //MARK: - Process
    for _ in 0..<n - 1 {
        guard let inputData: [String] = readLine()?.components(separatedBy: " ") else { return }
        let a: Int = inputData.map { Int($0) }[0] ?? 0
        let b: Int = inputData.map { Int($0) }[1] ?? 0
        
        parent[b] = a
    }
    
    while X != 0 {
        check[X] = true
        X = parent[X]
    }
    
    while Y != 0 {
        if check[Y] {
            break
        }
        Y = parent[Y]
    }
    
    //MARK: - Output
    print(Y)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.