백준 1967 트리의 지름

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

분류: 트리

---

접근방식

문제의 서두에 트리는 무방향 그래프라고 알려주면서 힌트를 주고 있습니다.

root가 있지만 방향성이 없기 때문에 트리를 돌려서 생각해보면
leaf 노드를 root로 한 트리의 형태를 생각해볼 수 있습니다.

root를 포함한 끝 노드에서 다른 끝 노드로 가는 경로가 이 트리의 지름이 됩니다 :)

 

해결방법

dfs를 돌려서 루트에서 가장 먼 노드를 찾고,
그 노드를 루트로 다시 dfs를 돌려서 가장 먼 지름는 방식으로 해결했습니다.

그 노드의 인접 노드들을 배열로 하는 이중 배열을 만들어서 해결했습니다.
트리가 익숙하지 않아서 이 자료구조를 만드는 데 꽤나 시간이 걸렸네요... 이게 최선인지도 모르겠습니다. 😢

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 BOJ1967: Readable {
    
    class Node {
        var value: Int
        var weight: Int
        
        init(_ value: Int, weight: Int) {
            self.value = value
            self.weight = weight
        }
    }
    
    func input() {
        for _ in 0..<readSingleValue()-1 {
            let n: [Int] = readArray(with: " ")
            nodes[n[0]].append(Node(n[1], weight: n[2]))
            nodes[n[1]].append(Node(n[0], weight: n[2]))
        }
    }
    
    var nodes = [[Node]](repeating: [Node](), count: 10001)
    var visited = [Bool](repeating: false, count: 10001)
    var maxDiameter = 0
    var farthestNodeFromRoot = 0
    
    func solution() {
        input()
        dfs(node: 1, weight: 0)
        visited = [Bool](repeating: false, count: 10001)
        dfs(node: farthestNodeFromRoot, weight: 0)
        print(maxDiameter)
    }
    
    func dfs(node: Int, weight: Int) {
        guard !visited[node] else { return }
        visited[node] = true
        
        if weight > maxDiameter {
            maxDiameter = weight
            farthestNodeFromRoot = node
        }
        
        for adj in nodes[node] {
            dfs(node: adj.value, weight: weight + adj.weight)
        }
    }
}

BOJ1967().solution()

배운점

트리에 익숙해지기... 이정도도 못하면 개발자 때려치자 😭