[백준] 16398번 : 행성 연결 - MST

MST 와 그리디

MST 알고리즘의 Kruscal, Prim 은 그리디 알고리즘에 속한다는 것 알고계시나요?
MST와 그리디 알고리즘에 대한 설명과 이해가 필요하다면 아래 블로그를 참고하시길 바랍니다 :)

• [알고리즘] MST
• [알고리즘] 그리디

문제

https://www.acmicpc.net/problem/1057

풀이

[백준] 1057번 : 토너먼트 🥈(실버4)
⏰ 걸린 시간 : 30분 -> 🔥 오답 필요 (떠오르지 않아서 참고함)

• 알고리즘 유형 : [MST(Kruscal & Prim)]
  

✔️ [문제 접근 방법]
0. Kruscal(크루스칼)과 Prim(프림) 두가지 알고리즘으로 접근이 가능하다.

📚 크루스칼 알고리즘

• 사이클의 유무를 찾기 위해서 Union - Find 알고리즘도 이용해야한다.

  1. 임의의 간선을 선택한다.
  2. Union - Find로 사이클을 검사하고
  3. 사이클을 이루지 않는다면 부모노드를 통일시킨다.
  4. 사이클을 이루지 않기때문에 연결된 간선의 길이도 더해준다.

  크루스칼 알고리즘 코드(code)

  import sys
  input = sys.stdin.readline
  
  # find parent 연산
  def find_parent(parent, x):
    if parent[x] != x:
      parent[x] = find_parent(parent,parent[x])
    return parent[x]
  
  # union parent 연산
  def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b:
      parent[b] = a
    else:
      parent[a] = b
  
  N = int(input())
  planets = []
  parent = [0] * (N+1)
  total_cost = 0
  
  for i in range(1,N+1):
    parent[i] = i
  
  # planet에 대한 입력을 받는 코드
  for i in range(N):
    row = list(map(int,input().split()))
    for j in range(i+1, N):
      planets.append((row[j], i, j))
  #  planets 오름차순 정렬
  planets.sort()
  
  
  # 크루스칼 알고리즘
  for i in range(len(planets)):
    cost, x, y = planets[i]
  # 만일 부모가 다르다면 연결해주고 해당 간선의 길이를 더해준다.
    if find_parent(parent,x) != find_parent(parent, y):
      union_parent(parent,x,y)
      total_cost += cost
  print(total_cost)
  

📚 프림 알고리즘

• 프림의 시간복잡도를 줄이기 위해서 최소힙(Min Heap) 자료구조를 이용해야한다.

  1. 임의의 정점을 선택한다.
  2. 해당 정점에서 갈 수 있는 간선을 최소힙(Min heap)에 넣는다.
  3. 최소값을 뽑아서 해당 정점을 방문하지 않았다면 선택한다.
  4. 선택한 간선들을 더해준다.

프림 알고리즘 코드(code)

import sys
from heapq import heappop,heappush
input = sys.stdin.readline

# 행성의 수
N = int(input())

planets = [[0]*(N+1)]
for i in range(N):
  row = [0] +list(map(int,input().split()))
  planets.append(row)
print(planets)
visited = [0]*(N+1)
def mst():
  q = []
  answer = 0
  q.append((0,1))
  while q : 
    len, planet = heappop(q)
    if visited[planet] == 0:
      answer += len
      visited[planet] = 1
      for next in range(1,N+1):
        if planets[planet][next] != 0 :
            heappush(q,(planets[planet][next], next))         
  return answer
print(mst())

회고

크루스칼 vs 프림 뭐가더 유리할까?

우선순위 큐를 사용한 프림 알고리즘의 시간복잡도인 O(Elog V+VlogV)과 비교했을 때 간선의 수가 적은 Sparse Graph의 경우 크루스칼 알고리즘이 유리하고 간선의 수가 많은 Dense Graph의 경우 프림 알고리즘이 유리하다.

• [해당 코드]

  [백준] 16398번 : 행성 연결 - MST