배고픈 개발자 이야기
[그래프] 가장 먼 노드 본문
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
'알고리즘 문제 > PROGRAMMERS' 카테고리의 다른 글
[ 연습문제 ] 롤케이크 자르기 (0) | 2022.11.09 |
---|---|
[2021 KAKAO BLIND] 신규 아이디 추천 (0) | 2021.10.07 |
[2020 kakao blind] 괄호변환 (0) | 2021.08.12 |
[2018 kakao blind] 뉴스클러스터링 (0) | 2021.08.10 |
[2021 카카오 인턴] 수식 최대화 (0) | 2021.08.07 |
Comments