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

 

문제풀이

처음에는 플로이드 와샬(O(n^3)) 을 사용했지만, 시간초과가 났다.

그 다음에는 다엑스트라(O(nlogn)) 을 사용했지만, 풀지 못했다.

그러다가 가장 쉽고 직관적인 BFS 를 사용해서 풀게되었다.

 

시간복잡도

O(n^2) 이하. (visited 에서 예외처리를 해주기 때문)

 

 

소스코드

from collections import deque
from collections import defaultdict;

def solution(n, edge):
    link = defaultdict(list);
    visited = [0] * (n+1);
    ret = [0] * (n+1);
    for a,b in edge:
        link[a].append(b);
        link[b].append(a);
    
    queue = deque();
    if link[1] == []:
        return 0;
    queue.append([1,0])
    visited[1] = 1;
    while queue:
        now, distance = queue.popleft();
        ret[now] = distance;
        for i in link[now]:
            if not visited[i]:
                visited[i] = 1;
                queue.append([i, distance+1]);
    
    maxV = max(ret);
    cnt = 0;
    for v in ret:
        if maxV == v:
            cnt += 1;
    return cnt;