문제

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

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

제한 사항

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

풀이

아이디어

• 우선 graph 배열을 만들고 노드 번호에 해당하는 인덱스에 각 노드와 연결된 노드들을 배열로 저장합니다.
• visited 배열을 만들어 모두 -1로 초기화해줍니다. -1이 가지는 의미는 이 노드를 아직 방문한 적이 없다는 표시입니다. visited 배열에는 1번부터의 최소 거리가 저장됩니다.
• BFS를 수행합니다.
  • queue의 맨 앞 노드(A)를 빼오고, 해당 노드와 연결된 노드들을 adjacents로 불러옵니다.
  • adjacents를 순회하며 다음 로직을 수행합니다.
    • 만약 visited 배열에서의 값이 -1이 아니라면, 방문했었다는 소리고, BFS이므로 그것이 저절로 최소 거리입니다. 따라서 별다른 조치를 하지 않습니다.
    • 만약 -1이라면, visited[A]의 값에 1을 더한 값을 visited[해당노드]에 저장합니다.
• BFS를 다 수행했다면 visited 배열이 완성되었을 겁니다. visited배열을 보면서, 저장되어있는 가장 큰 거리를 뽑아냅니다.
• 가장 큰 거리에 해당하는 노드들이 몇 개인지 Array.prototype.filter()를 이용해 뽑아내어 리턴합니다.

왜 BFS를 했는가?

(출처: 전현서님)

• DFS는 깊이를 우선 탐색하므로 엄청 빨리 최외곽에 있는 정점을 탐색할 수 있을겁니다. 그렇지만 모든 정점의 최소값의 거리를 계산해야하기 때문에 DFS는 다른 결과를 도출할 수도 있습니다. 물론 조건을 걸어서 최소값만 저장하면 되겠지만, 이 문제는 쓸데없는 행동이라도 보이면 시간초과를 만나는 무서운 문제입니다.
• BFS를 사용하면 어떨까요? BFS를 사용하면 1번정점부터 인접한 정점을 순서대로 탐색할 수 있습니다. 즉 가까운순으로 자동적으로 거리를 매길 수 있는 것이 됩니다. 굳이 최소값을 비교하여 정의 할 필요가 없습니다. 거리배열에 갱신되는 값은 자동적으로 항상 최솟값을 가지며 전부 탐색한 후에 거리배열에서 가장 큰 값의 개수를 반환하면 됩니다.

코드

function solution(n, edge) {
    //그래프 완성시키기
    const graph = new Array(n+1).fill().map(e => new Array());
    edge.forEach(e => {
        const [start, end] = e;
        graph[start].push(end);
        graph[end].push(start);
    });
    
    let visited = new Array(n+1).fill(-1);
    visited[1] = 0;
    
    bfs()
    
    //visited에는 레벨을 기록한다. (방문한 적 없으면 -1임)
    function bfs() {
        let queue = [1];
        
        while(queue.length) {
            const now = queue.shift();
            const adjacents = graph[now];
            
            for(let i=0; i<adjacents.length; i++) {
                if(visited[adjacents[i]] == -1) {
                    queue.push(adjacents[i]);
                    visited[adjacents[i]] = visited[now] + 1;
                }
            }
        }
    }
    

    
    //모든 visited가 완성되었다면 그 중 최대 레벨을 구한다.
    const maxLevel = Math.max(...visited);
    const maxOnly = visited.filter(num => num === maxLevel);
    
    return maxOnly.length;
}

파이썬 코드

from collections import defaultdict, deque

def solution(n, edge):
    dict = defaultdict(list)
    visited = [-1] * (n+1)
    
    #먼저 그래프의 정보를 채운다
    for s, e in edge:
        dict[s].append(e)
        dict[e].append(s)
    
    #1번부터 시작해서 BFS를 돌린다.
    maximum = -99
    
    def bfs():
        nonlocal maximum
        queue = deque([[1, 0]])
        while queue:
            node, cnt = queue.popleft()
            if visited[node] == -1:
                visited[node] = cnt
                if maximum <= cnt:
                    maximum = cnt
                adjacents = dict[node]
                for adj in adjacents:
                    if visited[adj] == -1:
                        queue.append([adj, cnt+1])
    
    bfs()
    return visited.count(maximum)