→ Problems
[Algorithm] 백준 - 1167번 트리의 지름 (Swift)
Swift librarian
2024. 5. 27. 13:23
문제 소개
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)