[BOJ] 백준 1167 트리의 지름 (Swift)

문제

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

풀이

DFS를 사용해서 풀 수 있습니다.

임의의 노드에서 출발하여 가장 먼 거리에 있는 노드를 탐색해줍시다.
임의의 노드에서 출발하여 가장 먼 거리에 있는 노드는 트리의 지름에 포함되는 노드입니다.

가장 먼 거리에 있는 노드를 찾았다면 그 노드에서 부터 가장 깊은 곳이 트리의 지름이 됩니다.

소스코드

	let n = Int(readLine()!)!
	var graph = [[(Int, Int)]](repeating: [], count: n + 1)
	var visited = [Bool](repeating: false, count: n + 1)
	for _ in 0..<n {
	let input = readLine()!.dropLast(2).split(separator: " ").map { Int($0)! }
	let node = input[0]
	var index = 1
	while index < input.count {
	graph[node].append((input[index], input[index + 1]))
	index += 2
	}
	}
	var endNode: (node: Int, cost: Int) = (node: 0, cost: 0)
	func dfs(node: Int, depth: Int) {
	visited[node] = true
	if depth > endNode.cost {
	endNode = (node, depth)
	}
	for (nextNode, distance) in graph[node] {
	if !visited[nextNode] {
	visited[nextNode] = true
	dfs(node: nextNode, depth: depth + distance)
	visited[nextNode] = false
	}
	}
	}
	dfs(node: 1, depth: 0)
	visited = [Bool](repeating: false, count: n + 1)
	dfs(node: endNode.node, depth: 0)
	print(endNode.cost)

view raw 트리의 지름.swift hosted with ❤ by GitHub

후기

처음에는 모든 노드에 대해 DFS나 다익스트라를 해봐야하나... 생각이 들었습니다.
하지만 정점의 개수가 최대 10만이므로, 두 방식으로는 시간초과가 나게됩니다.
블로그 글을 참고해서 풀이하였고, 이런 방법은 직접 떠올리지 못해서 아쉬웠습니다.😂