[알고리즘][Lv3]가장 먼 노드(python)(프로그래머스)

문제 풀기
1번 노드로부터 최단경로 기준 가장 멀리 있는 노드의 개수를 구하는 문제.

😀Ideation

• bfs로 탐색하는 queue 자료구조 활용
• 연결 정보는 각 노드별 연결된 노드가 담긴 구조를 dictionary 형태로 저장(defaultdict활용)
• distance 에 거리별로 count를 하나씩 늘려 감

from collections import deque
from collections import defaultdict

def solution(n, edge):
    que=deque()
    que.append(1) # 시작 노드
    distance = [0]*n #거리정보 count할 곳

    # 노드에 연결된 정보들 저장. defaultdict를 활용하면 숫자가 아니어도 dictionary 형태로 저장 가능
    dic=defaultdict(list)
    for key, value in edge:
        dic[key]+=[value]
        dic[value]+=[key]
    graph = dict(sorted(dic.items())) #1부터 n까지 정렬

    # print(graph) #그래프 정렬 확인

    while que:
        node = que.popleft() #node : 이전 노드
        for nod in graph[node]:
            # index는 0부터 시작이므로 -1 하기, nod : node와 연결된 노드들
            if distance[nod-1]==0 and nod!=1: # 1번 노드는 제외,node 값이 0이 아닌곳에
                distance[nod-1]=distance[node-1]+1  #1추가
                que.append(nod)

    # print(distance) #거리정보 확인

    #max값 확인
    maxv = max(distance)
    cnt=0
    for v in distance:
        if v==maxv:
            cnt+=1
    return cnt

수행 결과

n=6
edge=[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

solution(n,edge)

>>> 3 

3개가 가장 멀리 있다(4,5,6번 노드)