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

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

 

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

문제 설명

설명

입출력 및 그래프 형태

• vertex로 연결된 정점들이 주어진다.
  • 연결된 정점끼리의 간선은 모두 1이다.
• 1번 정점을 기준으로 하여 해당 정점에서 멀리 떨어진 정점의 개수를 반환하는 것이다
  • 떨어진 거리를 dist로 하여 배열에 저장을 한다
  • 이때 거리의 최댓값과 동일한 노드의 갯수를 반환하는 방식을 선택했다
• 거리를 측정하는 방법은 다익스트라 알고리즘을 사용
  • 각 정점끼리의 거리를 최대값 1e9로 초기값을 세팅
  • heapq를 사용하여 우선순위 큐를 사용
    • 효율적인 최단 거리를 가진 노드를 선택하기 위해서 사용한다.
    • 우선순위 큐는 각 요소를 우선순위에 따라 정렬된 상태로 저장을 하여 효율적으로 최소 값을 추출하는 데 사용된다

 

풀이 코드

 

import heapq
def solution(n, edge):
    maps = [[] for _ in range(n+1)]
    for i,j in edge:
        # 양방향 그래프
        maps[i].append((j,1))
        maps[j].append((i,1))

    dist = [1e9]*(n+1)
    
    q = []
    heapq.heappush(q, (0,1))
    dist[1] = 0
    
    while q:
        distance, now = heapq.heappop(q)
        if dist[now] <distance:
            continue
        for i in maps[now]:
            cost = distance + i[1]
            if cost < dist[i[0]]:
                dist[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
                
    for i in range(len(dist)):
        if dist[i] == 1e9:
            dist[i] = 0
            
    return dist.count(max(dist))