배고픈 개발자 이야기

[그래프] 가장 먼 노드 본문

알고리즘 문제/PROGRAMMERS

[그래프] 가장 먼 노드

이융희 2022. 11. 9. 16:40
728x90

n개의 노드와 연결되어 있는 간선 정보인 edge가 주어진다.

 

문제는 1번노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제이다.

 

- 풀이 -

1. edge로 graph를 간선간 가중치가 1인 형태로 먼저 저장한다.

2. 1번 노드를 start로, 2 ~ n번 노드를 destination으로 dijkstra로 최단거리를 각각 계산한다.

3. 최단거리의 max 값을 취한 후 동일한 거리를 가진 노드들의 개수를 센다.

 

- 결과 -

100점~

 

# programmers graph task
# https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=python3

import heapq
graph = {}

def dijkstra(start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    while queue:
        current_distance, current_destination = heapq.heappop(queue)

        if distances[current_destination] < current_distance:
            continue

        for new_destination, new_distance in graph[current_destination].items():
            distance = current_distance + new_distance
            if distance < distances[new_destination]:
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])
    
    return distances

def fill_graph(n, edge):
    for i in range(n):
        graph[i + 1] = dict()
    
    for line in edge:
        graph[line[0]][line[1]] = 1
        graph[line[1]][line[0]] = 1

def solution(n, edge):
    answer = 0
    path_list = list()
    fill_graph(n, edge)
    
    start = 1
    path_list = dijkstra(start)
    
    node_list = list(path_list.values())
    max_node_cnt = max(node_list)
    answer = node_list.count(max_node_cnt)
    
    return answer
Comments