Swift) 프로그래머스 가장 먼 노드 - Lv. 3

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

문제 풀이: 1번 노드를 시작점으로 각 노드마다 1번 노드와의 최단 거리를 구하는 것이 문제의 핵심. 1번 노드를 시작으로 BFS로 연결된 노드들을 큐에 넣어주고, 넣은 노드는 방문 처리해준다. 가장 처음에 만났을때가 최단 거리니까.. 

 

한가지 주의해야 할점은 n이 최대 20000개 이므로 각 노드별 연결되있는지 안되있는지 Bool로 판단하면 시간 초과가 뜨기 때문에

1 -> {1,2,3}

2 -> {1,5,6} 

3 -> {1,4,5}

이런식으로 연결되있는 경로를 지정하는 방식으로 구현했다.

import Foundation

struct Node {
    let distance: Int
    let num: Int
}

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var minDistance = Array(repeating: 0, count: n)
    var map: [[Int]] = Array(repeating: Array(repeating: 0, count: 0), count: n)
    var visited =  Array(repeating: false, count: n)
    for i in edge {
        map[i[0]-1].append(i[1]-1)
        map[i[1]-1].append(i[0]-1)
    }
    var queue: [Node] = [.init(distance: 0, num: 0)]
    visited[0] = true
    var idx = 0
    while queue.count > idx {
        let popNode = queue[idx]
        idx += 1
        for node in map[popNode.num] {
            if !visited[node] {
                minDistance[node] = popNode.distance+1
                queue.append(.init(distance: popNode.distance+1, num: node))
                visited[node] = true
            }
        }
    }
    let maxValue = minDistance.max()!
    return minDistance.filter{ $0 == maxValue }.count
}