[Swift] 백준 1167 - 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고(2<= V <= 100,000) 둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

문제 바로가기

풀이

임의의 두 점 사이 중 가장 긴 것을 트리의 지름으로 여긴다.
여기서 지름이 가장 길어지려면, 두 점은 우선 맨 끝 하위노드여야한다.

그렇다면, 존재하는 여러 하위 노드 중 어떤 두 점을 지름으로 여겨야 할 까?
=> 그 깊이가 가장 긴 노드이다.

따라서 풀이는 다음과 같은 순서로 진행되어야한다.

• dfs를 사용하여 가장 깊이가 깊은 하위노드를 구한다.
• 해당 하위노드에서 시작하여 가장 길이가 긴 끝점을 구한다
  • 이 길이가 지름이 된다.

dfs를 두 번 사용하면 되는 문제이다.

Swift 코드

import Foundation

let V = Int(readLine()!)!
var tree = Array(repeating: [(Int,Int)](), count: V+1)

for _ in 1...V {
	let arr = readLine()!.split(separator:" ").map{Int(String($0))!}
    var idx = 1
    while true {
    	if arr[idx] == -1 { break }
        tree[arr[0]].append((arr[idx],arr[idx+1]))
        idx += 2
    }
}

var visited = Array(repeating: false, count: V+1)
var finalNode = 0
var length = 0

func dfs(_ node: Int, _ depth: Int) {
	visited[node] = true
    
	if length < depth {
    	length = depth
        finalNode = node
    }
    
	for i in tree[node] {
    	if !visited[i.0] {
        	dfs(i.0, depth + i.1)
        }
    }
}

dfs(1,0)
length = 0
visited = Array(repeating: false, count: V+1)
dfs(finalNode,0)

print(length)