가장 먼 노드

문제

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

!https://grepp-programmers.s3.amazonaws.com/files/ybm/fadbae38bb/dec85ab5-0273-47b3-ba73-fc0b5f6be28a.png

접근 방식

처음 접근 방식

참고 : https://babbab2.tistory.com/106

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    // 그래프 만들기
    var graph = [Int: [Int]]()
    for arr in edge {
        let first = arr[0]
        let second = arr[1]
        
        if graph[first] == nil {
            graph[first] = []
        }
        if graph[second] == nil {
            graph[second] = []
        }

        graph[first]?.append(second)
        graph[second]?.append(first)
    }
    
    print("graph: \(graph)\n")
    
    func bfs(graph: [Int: [Int]], start: Int) -> Int {
        var needVisitQueue: [Int] = [start]
        var visitedQueue = [Int]()
        
        var count = [Int : Int]()
        while !needVisitQueue.isEmpty {
            let node: Int = needVisitQueue.removeFirst()
            if visitedQueue.contains(node) { continue }
            
            visitedQueue.append(node)
            needVisitQueue += graph[node] ?? []
            count[node, default: 0] += 1
        }
        return count.filter { $0.value == 0 }.count
    }
    let result = bfs(graph: graph, start: 1)
    return result
}

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

• 입력 배열 edge를 순회하며 그래프 생성
• 넓이 우선 탐색을 하기 위한 bfs 메서드 작성
• needVisitQueue : 방문해야 하는 노드
• visitedQueue : 방문 할 노드
• node : 현재 노드
• 현재 노드가 visitedQueue 에 있으면 통과, 없으면 추가 한 뒤 needVisitQueue 에 자식 노드 추가
• 추가 될 때 해당 노드의 자식 노드를 카운트 하도록 count[node, default: 0] += 1 하였다.

실패

• 자식 노드에 갈 때마다 count[node, default: 0] += 1 가 동작할 거라 생각하여 자식 노드가 없는 마지막 노드, 즉 가장 먼 노드의 카운트가 0이 될 거라 생각함.
• 자식 노드에 가는 게 아니라 visitedQueue에 값이 추가 될 때마다 해당 노드에 대한 카운트 count[Node]가 + 1이되어 모든 노드에 대한 카운트만 된, [1, 1, 1, 1, 1, 1]이 나오게 됨.

다른 방식

func bfs(graph: [Int: [Int]], start: Int) -> Int {
        var needVisitQueue: [Int] = [start]
        var distance = Array(repeating: -1, count: n+1)
        
        distance[start] = 0
        
        while !needVisitQueue.isEmpty {
            let node: Int = needVisitQueue.removeFirst()
            for neighbor in graph[node, default: []] {
                if  {
                    distance[neighbor] = distance[node] + 1
                    needVisitQueue.append(neighbor)
                }
            }
        }
        
        let maxDistance = distance.max()
        let count = distance.filter { $0 == maxDistance }.count
        return count
        }

접근 방식

• 거리(간선 수)에 대한 배열을 노드 수+1만큼 미리 만들고 기본값으로 -1 넣기
• 기준이 되는 시작 노드의 거리 값은 0으로 초기화
• 현재 노드인 node의 하위 노드를 순회하며 방문했던 노드인지 확인 (if distance[neighbor] == -1)
• 방문한 적 없는 노드면 거리 값 업데이트 후 해당 하위 노드를 큐에 추가해 연결된 더 하위의 노드 순회 준비
• 작성된 거리 중 가장 큰 값 저장 후 같은 값의 수 반환

---

배운 점

저번에 DFS할 때와 비슷한듯 다른 알고리즘이었다.

일단 노드의 관계를 만드는 그래프 정도는 DFS를 몇 문제 했어서 그런가 어렵지 않게 만들 수 있었고,
bfs 메서드 만드는 것도 어느정도는 접근했는데, 거리에 대한 배열을 만드는 아이디어를 생각해내기가 너무 어려웠다.

DFS에서 백트래킹이 필요했을때도 비슷하게, 뭔가 한 스텝이 부족한데 뭘까 고민했는데 이번에도 마찬가지였다..

그래도 DFS 문제 처음 풀 때 어떻게 접근해야 할지 감도 잡지 못하고, '이걸 내가 할 수 있는 레벨의 문제가 맞나?' 싶었는데, 그래도 2주에 걸쳐서 DFS 몇 번 했다고 BFS는 그렇게까지 낯설진 않았다.

아직 많이 어렵지만 또 한편으론 재밌기도 해서, 예방주사라고 생각하고 더 고민하는 시간을 가져봐야 할 것 같다..!