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

programmers.co.kr/learn/courses/30/lessons/49189

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

간단하게는

1번에서부터 먼 거리에있는 노드를 찾는 문제에요

 

뭔가 bfs를 사용해야할거같죠..?

막상 하려니 감이안오네요 ㅎㅎ

bfs는 큐를 사용하니까 큐를 이용해서 구현해볼거에요

 

해결 방법

제가 생각한 원리로는

1번에서 시작하면 인접한 노드는 [2, 3] 가있고

거리가 1이다를 저장할거에요

큐를 두개만들고 하나는 꺼내는용 하나는 결과 저장용이에요

(2, 1), (3, 1) 이 두개를 두개의 큐에 저장해두고

 

꺼내는용큐:(2, 1), (3, 1)

저장큐:(2, 1), (3, 1)

 

꺼내는용 큐에있는 내용을 꺼내와요 꺼내면 (2, 1)가있겟죠?

2에 인접한 노드들을 다시 불러오면

[4, 5] 가 되겠네요

그럼 4, 5는 각각 거리가 2잖아요?

그럼 (4, 2), (5, 2) 가 될거에요

두개의 큐에 저장해주고

 

꺼내는용큐: (3, 1), (4, 2), (5, 2) 

저장큐:(2, 1), (3, 1), (4, 2), (5, 2) 

 

끝낫다면 다시 꺼내는용큐에서 하나를 꺼내와서

반복하는 원리에요

 

이작업을 하면서 갔던곳을 또가게되면 비효율적이니까

처리를 따로해주도록하구요

private func solutionP49189(_ n:Int, _ edge:[[Int]]) -> Int {
    
    var tree: [Int: [Int]] = [:]
    
    func insertTree(key: Int, value: Int) {
        if tree.keys.contains(key) {
            tree[key]?.append(value)
        } else {
            tree[key] = [value]
        }
    }
    
    for e in edge {
        insertTree(key: e[0], value: e[1])
        insertTree(key: e[1], value: e[0])
    }
    
    var queue: [(Int, Int)] = []
    var result: [(Int, Int)] = []
    var visited: [Bool] = Array(repeating: false, count: tree.keys.count)
    func bfs(key: Int, depth: Int) {
        for node in tree[key]! {
            if visited[node-1] {
                continue
            }
            visited[node-1] = true
            result.append((node, depth))
            queue.append((node, depth))
        }
    }
    
    queue.append((1,0))
    visited[0] = true
    while !queue.isEmpty {
        let node = queue.removeFirst()
        bfs(key: node.0, depth: node.1+1)
    }
    
    let maxNum = result.max {$0.1 < $1.1}.map {$0.1}
    var count = 0
    for node in result {
        if maxNum == node.1 {
            count += 1
        }
    }
    
    return count
}