[프로그래머스] 가장 먼 노드 with Swift

• 연습문제
• 가장 먼 노드
• Level 3

 

문제

• n개의 노드가 있는 그래프
• 1번 노드에서 가장 멀리 떨어진 노드의 개수 구하기
• 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때, 간선의 개수가 가장 많은 노드들을 의미

 

• n은 2이상 20,000이하
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있음
• 간선 정보는 [a, b] 배열로 제공되는데, 이는 a번 노드와 b번 노드 사이에 간선이 있다는 의미

 

Idea

Dijkstra

• 연결된 간선의 개수에 따라 최단 경로가 결정되므로 모든 가중치는 1로 가정하여 각 노드의 비용을 구하면 됨

 

Code

Swift

• 다익스트라 알고리즘으로 구현

► 다익스트라 알고리즘 with Swift

다익스트라 알고리즘 with Swift

• 본래는 힙을 사용해야 하나, 직접 구현해야 해서 대신 sort 를 사용했는데 그렇게 되면 9번 테스트케이스에서 시간초과가 발생함
• 하지만 모든 거리가 1이기 때문에 결국 큐에 추가된 순서대로 거리가 정렬됨
• 따라서 정렬 코드를 삽입할 필요가 없음

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    
    var graph = Array(repeating: [Int](), count: n+1)
    for info in edge {
        graph[info[0]].append(info[1])
        graph[info[1]].append(info[0])
    }
    
    var costs = Array(repeating: Int.max, count: n+1)
    var s = Array(repeating: false, count: n+1)
    
    func dijkstra(start: Int) {
        
        costs[0] = 0
        costs[start] = 0
        var queue = [start]
        while !queue.isEmpty {
            // queue.sort { $0.1 < $1.1 }
            let node = queue.removeFirst()
            s[node] = true
            
            for next in graph[node] {
                if !s[next], costs[node] + 1 < costs[next] {
                    costs[next] = costs[node] + 1
                    queue.append(next)
                }
            }
        }
    }
    dijkstra(start: 1)
    
    let max = costs.max()
    return costs.filter { $0 == max }.count
}