코딩테스트 연습 - 가장 먼 노드

문제 풀이 아이디어

최단 경로 == bfs

최단 경로를 구하는 문제는 bfs를 사용하면 됩니다.

인접 리스트를 활용해서 성능을 높이자!

입력으로 주어지는 edge를 사용해서 bfs를 하면 한 node에서 다른 node로 가는 간선을 찾기위해서 매번 O(N)의 탐색을 해야합니다. 인접리스트를 사용하면 O(1)로 성능을 개선할 수 있습니다.

코드

// Queue 구현
struct Queue {
    var index = 0
    var queue = [Int]()
    
    var isEmpty: Bool {
        queue.count == index
    }
    
    mutating func push(_ t: Int) {
        queue.append(t)
    }
    
    mutating func pop() -> Int {
        defer {
            index += 1
        }
        return queue[index]
    }
}

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    
    // 속도가 중요하므로 인접리스트를 사용
    var edgeList = Array(repeating: [Int](), count: n + 1)
    
    // 인접 리스트에 간선 저장
    for e in edge {
        let from = e[0]
        let to = e[1]
        edgeList[from].append(to)
        edgeList[to].append(from)
    }
    
    // bfs를 위한 Queue
    var queue = Queue()
    // node 1에서부터의 거리를 저장하는 배열
    var distance = Array(repeating: -1, count: n + 1)
    
    // 1번 node queue에 넣고 거리 저장
    queue.push(1)
    distance[1] = 0
    
    // bfs 실행하면서 거리 저장
    while !queue.isEmpty {
        let now = queue.pop()
        for i in edgeList[now] {
            if distance[i] < 0 {
                queue.push(i)
                distance[i] = distance[now] + 1
            }
        }
    }
    
    // max()는 O(N)이므로 filter 밖에서 해주어야 함!
    let max = distance.max()!
    
    // 거리의 최댓값의 갯수를 리턴
    return distance.filter { $0 == max }.count
}

🚫 주의

제가 처음에 아래와 같이 코드를 짰다가 시간초과를 맞았습니다. max()는 O(N)인데 filter 안에서 사용하면 고차함수 filter가 해당 클로저를 실행할 때마다 계속 O(N)의 max()를 실행합니다. 이런 실수를 하지 않도록 해야겠습니다!

return distance.filter { $0 == distance.max()! }.count