1️⃣ 문제
2️⃣ 풀이 방법 및 코드
정점 별 인접리스트 edges를 가지는 Struct로 그래프 타입을 만들어 주었다.
그 노드들을 BFS로 순회하여 최단거리 구하면 끄읕
1️⃣ 로직
-
정점(Graph[i])마다 간선 연결하기
-
1에서 2, …, N까지의 최단 거리를 BFS로 구하기
-
최단 거리 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만 들여다보면서 삽질함.. ^_^)
클린코드도 중요하지만, 늘 시간복잡도 고려하자!!!