백준 11725 트리의 부모 찾기

출처: https://www.acmicpc.net/problem/11725

분류: 트리, 그래프 탐색

---

접근방식

우선 주어진 대로 트리를 모두 연결하고 루트 노드부터 부모를 연결해나가면 되는 문제입니다!

연결된 노드를 우선 connects에 담아두고 부모가 결정되면 connects에서는 지워주는 방식으로 구현했어요!

처음엔 연결 할 때마다 체크하려고 했는데 다 연결하고 수정해나가는 건 쉬운데, 이건 만만치 않더라구요..

해결방법

import Foundation

protocol Readable {
    func readSingleValue() -> String
    func readArray(with separator: Character) -> [String]
}

extension Readable {
    func readSingleValue() -> String {
        return readLine()!
    }
    
    func readSingleValue() -> Int {
        return Int(readLine()!)!
    }
    
    func readArray(with separator: Character) -> [String] {
        return readLine()!.split(separator: " ").map { String($0) }
    }
    
    func readArray(with separator: Character) -> [Int] {
        return readLine()!.split(separator: " ").map { Int(String($0))! }
    }
}

class BOJ11725: Readable {
    class Tree {
        class Node: Hashable {
            var parent: Node?
            var connects: Set<Node>
            var value: Int
            
            init(_ value: Int) {
                self.value = value
                self.connects = []
            }
            
            static func == (lhs: BOJ11725.Tree.Node, rhs: BOJ11725.Tree.Node) -> Bool {
                return lhs.value == rhs.value
            }
            
            func hash(into hasher: inout Hasher) {
                hasher.combine(value)
            }
        }
        
        let rootValue = 0
        var root: Node
        var nodes = [Node]()
        
        init(size: Int) {
            self.root = Node(rootValue)
            self.nodes = (rootValue...size).map { Node($0) }
        }
        
        func connect(_ current: Int, with other: Int) {
            nodes[current].connects.insert(nodes[other])
            nodes[other].connects.insert(nodes[current])
        }
        
        func connectParent(to node: Node) {
            for child in node.connects {
                child.parent = node
                child.connects.remove(node)
                connectParent(to: child)
            }
        }
        
        func printAllParentsOfNodes() {
            nodes.forEach {
                guard let parent = $0.parent else { return }
                print(parent.value+1)
            }
        }
    }
    
    func solution() {
        let n: Int = readSingleValue()
        let tree = Tree(size: n)
        
        for _ in 0..<n-1 {
            let connect: [Int] = readArray(with: " ")
            tree.connect(connect[0]-1, with: connect[1]-1)
        }
        
        tree.connectParent(to: tree.nodes[0])
        tree.printAllParentsOfNodes()
    }
}

let boj = BOJ11725()
boj.solution()

 

배운점

🎄