1. 문제 설명

가장 먼 노드

2. 문제 분석

BFS를 통해 현재 도달한 노드가 리프 노드인지 확인할 수 있다. 리프 노드라면 시작 노드에서 거슬러 온 노드의 개수가 곧 그 리프 노드에 대한 키가 된다. 키의 값을 +1 해주자. BFS 방문이 모두 끝났을 때 딕셔너리의 키 값 중 최댓값에 해당하는 값이 곧 원하는 답이다.

3. 나의 풀이

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var nodes = Array(repeating: [Int](), count:n+1)
    for data in edge {
        let node1 = data[0]
        let node2 = data[1]
        nodes[node1].append(node2)
        nodes[node2].append(node1)
    }
    let answer = BFS(start: 1, nodes: nodes)
    return answer
}

func BFS(start: Int, nodes: [[Int]]) -> Int {
    var queue = [(Int, Int)]()
    var visited = Array(repeating: false, count: nodes.count + 1)
    queue.append((start, 0))
    visited[start] = true
    var index = 0
    var leafDict = [Int:Int]()
    while queue.count > index {
        let curData = queue[index]
        let curNode = curData.0
        let curCost = curData.1
        
        var isLeaf = true
        for nextNode in nodes[curNode] {
            if !visited[nextNode] {
                isLeaf = false
                visited[nextNode] = true
                queue.append((nextNode, curCost + 1))
            }
        }
        if isLeaf {
            let leafValue = leafDict[curCost] ?? 0
            leafDict[curCost] = leafValue + 1
        }
        index += 1
    }
    let farthest = leafDict.keys.max() ?? 0
    return leafDict[farthest] ?? 0
}