1. 문제 설명

트리의 지름

2. 문제 분석

BFS를 통해 주어진 트리 그래프 내 시작 노드에서 가장 길이가 먼 (가중치 누적합이 가장 큰) 노드를 리턴할 수 있다. 이를 이용해 트리의 '지름'을 파악하자. 루트 노드로부터 시작해 1). 루트에서 가장 떨어진 노드가 무엇인지 리턴하자. 2). 이 노드에서 연결된 다른 모든 노드까지 걸리는 최대 길이를 리턴하자.

3. 나의 풀이

import Foundation

let N = Int(String(readLine()!))!
var nodes = Array(repeating: [(Int, Int)](), count: N+1)

for _ in 0..<(N-1) {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (parent, child, cost) = (input[0], input[1], input[2])
    
    nodes[parent].append((child, cost))
    nodes[child].append((parent, cost))
}

let nodeInfo1 = BFS(start: 1)
let node1 = nodeInfo1.0
let nodeInfo2 = BFS(start: node1)
let cost = nodeInfo2.1

print(cost)

func BFS(start: Int) -> (Int, Int) {
    var queue = [(Int, Int)]()
    queue.append((start, 0))
    var visited = Array(repeating: false, count: N+1)
    visited[start] = true
    var localMaxCost = 0
    var localMaxNode = start
    var index = 0
    
    while queue.count > index {
        let curData = queue[index]
        
        let curNode = curData.0
        let curCost = curData.1
        
        if localMaxCost < curCost {
            localMaxCost = curCost
            localMaxNode = curNode
        }
        
        for nextData in nodes[curNode] {
            let nextNode = nextData.0
            let nextCost = nextData.1
            
            if !visited[nextNode] {
                visited[nextNode] = true
                queue.append((nextNode, curCost + nextCost))
            }
        }
        index += 1
    }
    return (localMaxNode, localMaxCost)
}