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

문제출처: https://programmers.co.kr/learn/courses/30/lessons/49189

접근법

처음에는 1번 노드부터 dfs 알고리즘을 통해 확인하는 방법을 사용했으나 이는 처음 한번 최단거리를 확인한 노드들도 또 방문하는 비효율적인 알고리즘 선택이라는 것을 알게되었다.
( 7,8,9번 테스트케이스에서 시간초과 )

최단거리를 확인하는 알고리즘은 bfs 알고리즘이 적절하다.
1. 큐에 1번노드를 넣는다.
2. 큐에 헤드를 POP한 뒤 그 노드번호가 아직 방문하지 않는 노드들에 대한 간선이 존재한다면 큐에 푸쉬한다.

• 큐에 푸쉬할때 현재까지 몇개의 노드를 방문했는지의 정보를 set 자료구조를 통해 저장한다.( n , index+1 )
• 큐의 헤드에서 꺼냈을때 해당 노드번호의 최단거리는 (cur,index) 중 index가 될 것이다. ( 1번 노드부터 거리를 1씩 늘려가며 중복을 확인하며 큐에 집어넣었기 때문에 노드들은 한번씩 나올 것이다. )
• 방문하지 않은 노드들은 defaultdict를 통해 어떠한 키에 대하여 기본값 0 을 가지기 때문에 방문표시를 하지 않는 한 0을 가지기 때문에 관리가 수월하다.
  ( 이 문제는 노드 번호가 1번부터 n번을 가지지만 노드번호가 특정되어 있지 않을때 유용할 것 같다.)

코드

from collections import defaultdict
def solution(n, edge):
    answer = 0
    d = defaultdict(list)
    for i,j in edge:
        d[i].append(j)
        d[j].append(i)
    v = defaultdict(int)
    a = defaultdict(int)
    q = [(1,0)]
    v[1] = 1
    while( q ):
        cur,index = q.pop(0)
        a[cur] = index
        for n in d[cur]:
            if( v[n] == 0 ):
                v[n] = 1
                q.append((n,index+1))
    m = max( a.values() )
    for i in a.values():
        answer += 1 if(i==m) else 0
    return answer