프로그래머스 그리디 문제

크루스칼 알고리즘

• 크루스칼 알고리즘은 모든 정점을 가장 짧은 거리내에 방문하고 싶을 때 사용되는 알고리즘이다.

def solution(n, costs):
    total = 0
    uni = [i for i in range(n+1)]
    costs.sort(key=lambda x: x[-1])
    print(costs)
    
    def find(x):
        if x == uni[x]:
            return x
        else:
            uni[x] = find(uni[x])
            return find(uni[x])
    
    def union(x, y):
        # a는 x의 부모 노드
        a = uni[x]
        
        # b는 y의 부모 노드
        b = uni[y]
        
        # a의 부모 노드를 b로 설정함 (즉, 두 개의 부모 노드를 같게 설정함)
        if a != b:
            uni[a] = b
    
    for cost in costs:
        v, w, c = cost
        # v의 부모 노드와 w의 부모 노드가 다를시에 union을 통해 부모 노드를 같게 만듬
        if find(v) != find(w):
            union(v, w)
            total += c
    
    return total

• 크루스칼 알고리즘은 union & find 방식을 통해 풀 수 있다.

다익스트라 알고리즘

• 다음과 같은 그래프가 주어지고 시작점에서 다른 노드까지의 가장 가까운 거리를 구하는 것이 다익스트라 알고리즘이다.

graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

솔루션은 다음과 같다:

import heapq

def dijkstra(graph, start):
  # 시작점부터 각 노드까지의 거리를 무한대로 초기화함
  distances = {node: float('inf') for node in graph}
  queue = []
  distances[start] = 0
  heapq.heappush(queue, [start, distances[start]])
  
  while queue:
  # 현재 노드에서 가장 가까운 위치에 있는 노드를 선택함
    current_des, current_dis = heapq.heappop(queue)
  
  # 기존에 있는 길이보다 길다면, 볼 필요도 없음
    if distances[current_des] < current_dis:
      continue
  
  # next_dis는 현재 노드에서 가장 가까운 노드가 가리키고 있는 다른 노드까지의 거리
    for next_des, next_dis in graph[current_des].items():
      distance = current_dis + next_dis
      if distance < distances[next_des]:
        distances[next_des] = distance
        heapq.heappush(queue, [next_des, distance])
        
  return distances