1️⃣ 문제

문제 - 가장 먼 노드

2️⃣ 풀이 방법 및 코드

정점 별 인접리스트 edges를 가지는 Struct로 그래프 타입을 만들어 주었다.

그 노드들을 BFS로 순회하여 최단거리 구하면 끄읕

1️⃣ 로직

  1. 정점(Graph[i])마다 간선 연결하기

  2. 1에서 2, …, N까지의 최단 거리를 BFS로 구하기

  3. 최단 거리 max값을 가지는 노드 개수 return

2️⃣ 소스 코드

import Foundation

struct Graph {
    var edges: [Int]
    
    init() {
        self.edges = []
    }
}

func bfs(_ start: Int, _ visited: inout [Bool], _ graph: inout [Graph], _ distances: inout [Int]) {
    var queue = [Int]()
    var count = 0
    distances[start] = 0
    visited[start] = true
    queue.append(start)
    
    
    while !queue.isEmpty {
        let current = queue.removeFirst()
        
        for i in 0..<graph[current].edges.count {
            let next = graph[current].edges[i]
            
            if !visited[next] && distances[next] > distances[current] + 1 {
                distances[next] = distances[current] + 1
                visited[next] = true
                queue.append(next)
            }
        }
    }
}

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph = [Graph](repeating: Graph(), count: n + 1)
    var visited = [Bool](repeating: false, count: n + 1)
    var distances = [Int](repeating: Int.max, count: n + 1)
    
    // 1. 노드에 간선 연결하기
    for e in edge {
        graph[e[0]].edges.append(e[1])
        graph[e[1]].edges.append(e[0])
    }
    
    // 2. 1에서 2~N까지 최단거리를 BFS로 구하기
    bfs(1, &visited, &graph, &distances)
    
    // 3. 가장 먼 노드 구하기
    distances.removeFirst() // 0번 제거
    let max = distances.max()!
    let answer = distances.filter { $0 == max }.count
    
    return answer
}

3️⃣ 이 문제를 풀면서 되새긴 점

max() 의 시간복잡도: O(n)

처음에는 간결하게 고차함수를 쓰고 싶은 마음에, 아래 코드처럼 filter 클로저 안에 array.max() 함수를 사용했었다.

let answer = distances.filter { $0 == distances.max()! }.count

그러나, filter도 array를 O(n)만큼 탐색하기 때문에, 한번 탐색할 때마다 또 O(n)번 max값을 찾으므로 O(n^2)이 걸려 히든 테케 3개가 시간초과가 떴었다..

(저거 때문인지도 모르고 bfs만 들여다보면서 삽질함.. ^_^)

클린코드도 중요하지만, 늘 시간복잡도 고려하자!!!