[Algorithm/Programmers] 가장 먼 노드 Swift

가장 먼 노드 Level 3 BFS

 

문제 풀이:

1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 합니다. -> 1번 노드에서 시작한다.

가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. -> 모든 간선의 거리는 동일하다. -> BFS

 

주어진 간선을 이용해서 노드의 번호와 배열의 인덱스가 같은 배열을 만들어 그래프로 사용하고

노드의 번호와 배열의 인덱스가 같은 배열을 만들어 1번 노드로부터 떨어진 거리를 저장할 용도로 사용한다.

그리고 시작노드를 큐에 넣고 그래프에 연결되고 방문한 적이 없는 다음 노드로 넘어가면서 현재 노드의 거리에 1씩 더해서 다음 노드에 저장한다. 또한 큐에 다음 노드를 넣는다. 

큐에 있는 노드를 다 순회할 때까지 반복한다.

 

코드:

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    // 1번 노드로부터의 거리
    var distance = [Int](repeating: 0, count: n+1)
    var graph = [[Int]](repeating: [Int](), count: n+1)

    for i in edge.indices {
        // 간선 양방향
        graph[edge[i][0]].append(edge[i][1])
        graph[edge[i][1]].append(edge[i][0])
    }

    bfs(&distance, graph)
    // 제일 먼 거리를 기준으로 내림차순 정렬
    distance.sort(by: >)
    // 제일 먼 거리와 같은 거리의 개수 반환
    return distance.filter { $0 == distance.first }.count
}

func bfs(_ distance: inout [Int], _ graph: [[Int]]) {
    var q = [Int]()
    // 1번 시작 노드 초기화
    q.append(1)
    distance[1] = 1
    // 시간을 줄이기 위해 인덱스로 큐 순회
    var idx = 0
    while idx < q.count {
        let now = q[idx]
        idx += 1

        for next in graph[now] where distance[next] < 1 {
            distance[next] = distance[now] + 1
            q.append(next)
        }
    }
}

print(solution(6, [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]))

 

문제:

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