[Algorithm] 백준 - 1167번 트리의 지름 (Swift)

문제 소개

https://www.acmicpc.net/problem/1167
트리의 지름을 출력하는 문제이다.

문제 풀이

한 점에서 가장 먼 노드를 구한뒤, 그 노드에서 가장 먼 곳을 구하면 된다.

import Foundation

let n = Int(readLine()!)!
var tree = [Int: [(node: Int, cost: Int)]]()

for i in 1...n {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    tree[input[0]] = []
    
    for j in 0..<(input.count-1)/2 {
        let idx = j * 2 + 1
        tree[input[0]]?.append((input[idx], input[idx+1]))
    }
}

var point = 1
var maxCost = 0
var visited = Array(repeating: false, count: n+1)

func dfs(_ node: Int, _ cost: Int) {
    var next = false
    
    for nod in tree[node]! {
        if !visited[nod.node] {
            visited[nod.node] = true
            next = true
            dfs(nod.node, cost + nod.cost)
        }
    }
    
    if !next && cost > maxCost {
        point = node
        maxCost = cost
    }
}

visited[point] = true
dfs(point, maxCost)

visited = Array(repeating: false, count: n+1)
visited[point] = true
dfs(point, 0)

print(maxCost)