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

문제

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

프로그래머스

 

풀이

각 depth에 존재하는 노드의 개수를 묻는 문제였다. 그중 가장 멀리 있는 노드의 개수를 묻는 것이었고, BFS의 기본적인 유형 중 하나인 것 같았다. 큰 응용은 없었던 것 같고, 쉽게 BFS를 떠올릴 수 있었다. queue를 활용하여 BFS로 풀었다. 

코드에 대한 설명은 코드에 주석으로 달았다! 

 

코드

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var ans = [Int]()
    var queue = [1]
    var graph = [Int:[Int]]()
    // 초기값으로 1번 노드를 탐색했다고 선언하기 위해 이렇게 visited를 할당해주었다.
    var visited = [true] + Array(repeating: false, count: n-1)
    
    // 인접 리스트 형태로 graph를 그린다
    for each in edge {
        graph[each[0], default: []].append(each[1])
        graph[each[1], default: []].append(each[0])
    }
    
    // queue를 활용한 bfs로 노드를 탐색한다
    while !queue.isEmpty {
        // 각 depth마다 존재하는 노드를 카운트하기 위해 값을 초기화해준다. 나중에 leaf 노드 탐색이 되기 때문에 count = 0 값을 마지막에 빼주어야 한다.
        var count = 0
        
        // 각 depth에 존재하는 node만큼만 탐색한다.
        for _ in 0..<queue.count {
            let current = queue.removeFirst()
            for each in graph[current] ?? [] {
                if !visited[each-1] {
                    queue.append(each)
                    visited[each-1] = true
                    count += 1
                }
            }
        }
        
        // count를 ans 배열에 더해준다.
        ans.append(count)
    }
    
    // 추가된 leaf node 부분의 count값(0) 제거 
    ans.removeLast()
    return ans.last!
}