각 노드마다 bfs 적용함

no_4_sol.py

from collections import defaultdict, deque


def solution(edges):
    graph = defaultdict(list)
    for (n1, n2) in edges:
        graph[n1].append(n2)
        graph[n2].append(n1)


    answer = 0
    def bfs(start):
        nonlocal answer
        queue = deque([(start, 0)])
        visited = set()
        while queue:
            n, path_len = queue.popleft()

            if path_len > 1:
                answer += (path_len-1)

            for other in graph[n]: 
                if other not in visited:
                    queue.append((other, path_len+1))
                    visited.add(n)

    for n in graph:
        bfs(n)

    return answer

if __name__ == '__main__':
    edges = [[0,1],[0,2],[1,3],[1,4]]
    edges = [[2,3],[0,1],[1,2]]
    print(solution(edges))

다만 이렇게 하면 O(N*(N+logN)) 시간복잡도가 되어 시간초과가 날 것 같음