★[알고리즘 학습_MST_python_파이썬]백준_1197번_최소스패닝트리_MST_알고리즘 기초

공부하는허딩크 : https://www.youtube.com/live/0i-zE5mSAH0?feature=shared

 

MST(Minimum Spanning trees) 알고리즘의 기본문제는 골드4 레벨이다....

일단 그냥 학습하자.

참고 영상(영상 초반 이해가 안되고 어렵다. 끝까지 보면 조금 이해됨) : https://youtu.be/nZ4RTuoHS_Y?feature=shared

 

<요약>

1. 아래 기본 알고리즘을 그냥 외우자 : MST알고리즘을 모르고 문제를 해결하기 너무 어렵다.

2. MST 문제인지 알아내야한다. : 모든 노드가 연결되도록 한다거나, 이미 연결된 노드를 최소의 비용으로 줄인다거나..

 

<기본 알고리즘 코드>

import sys

import heapq

input = sys.stdin.readline

V, E = map(int, input().split())

edge = [[] for _ in range(V + 1)]

chk = [False] * (V + 1)

rs = 0

for i in range(E):

    a, b, c = map(int, input().split())

    edge[a].append([c, b])

    edge[b].append([c, a])

heap = [[0, 1]]

while heap:

    w, each_node = heapq.heappop(heap)

    if chk[each_node] == False:

        chk[each_node] = True

        rs += w

        for next_edge in edge[each_node]:

            if chk[next_edge[1]] == False:

                heapq.heappush(heap, next_edge)

               

print(rs)

 

<알고리즘 읽기>

"""

V = 3

E = 3

edge = [[], [[1, 2], [3, 3]], [[1, 1], [2, 3]], [[2, 2], [3, 1]]]

처음 heap = [[0, 1]] 준건 1번 노드부터 시작해서 1번 노드의 가중치는 0임

while문을 돌면서

heap = [[0, 1]]

1.  w = 0, each_node = 1

    if chk[1] == False이므로 chk[1] = True

    rs += 0

    ※edge[1] = [[1, 2], [3, 3]]이므로

    next_edge = [1, 2] and [3, 3]

    if chk[2] == False이므로

    heap에 [1, 2] 추가

    if chk[3] == False이므로

    heap에 [3, 3] 추가

heap = [[1, 2], [3, 3]]

2.  w = 1, each_node = 2

    if chk[2] == False이므로 chk[2] = True

    rs += 1

    edge[2] = [[1, 1], [2, 3]]이므로

    next_edge = [1, 1] and [2, 3]

    if chk[1] == False가 아니므로 pass

    if chk[3] == False이므로

    heap에 [2, 3] 추가

heap = [[2, 3], [3, 3]]

3.  w = 2, each_node = 3

    if chk[3] == False이므로 chk[3] = True

    rs += 2

    edge[3] = [[2, 2], [3, 1]]

    next_edge = [2, 2] and [3, 1]

    if chk[2] == False가 아니므로 pass

    if chk[3] == False가 아니므로 pass

heap = [[3, 3]]

4.  w = 3, each_next = 3

    if chk[3] == False가 아니므로 모두 pass

5. heap이 비어서 while문 종료

6. 최종 rs = 1 + 2

"""

 

<알고리즘 설명>

1. MST : 최소 비용으로 모든 노드가 연결된 트리 : 모든 노드의 연결된 트리가 효율적으로 중복되지 않게 연결되는 조건

2. 해결 방법 : Kruskal or Prim

    1) Kruskal : Union-Find 알고리즘 사용으로 어려우니까 나중에 고레벨되면 다시 보자.(기억할 수 있을까....)

2) 전체 간선 중 작은것부터 연결 : 간선 주황색 사각형

3) 설명 :

 - 우선 노드 1부터 시작해서 간선 1은 (1, 5)가 연결됨

 - 간선 2는 (1, 2) / 간선 3은 (1, 4) 

 - 간선 4는 (2, 4)인데 해당 노드는 2 - 1 - 4로 연결되어 있어

    필요 없음

 - 간선 5는 (2, 3) 

 - 간선 6은 (3, 4)인데 해당 노드는 3 - 2 - 1 - 4로 연결되어 있어 필요 없음

 

   

  ★ Prim : 현재 연결된 트리에 이어진 간선중 가장 작은 것을 추가 (일단 이해 안되도 코드 보고 와서 다시 보세요)

      - 노드 1번부터 시작

      - 간선이 작은 1부터 추가해줌 : 노드 (1, 5) 연결

      - 간선 2 : 노드 (1, 2) 연결

      - 간선 3 : 노드 (1, 4) 연결

      - 간선 4 : 노드 (2, 4) 연결해야 하나 이미 해당 간선은 방문한 이력이 있는 걸로 되어 필요 없음

             ㄴ 2번 방문 이력 있음, 4번 방문 이력 있음 (위 코드 설명 참고)

      - 간선 5 : 노드 (2, 3) 연결

      - 간선 6 : 노드 (3, 4) 연결해야 하나 간선 4와 동일

 

3. 순서 (아이디어)

 - 간선을 인접리스트에 집어넣기 : [무게, 노드번호]  # 무게 : 간선을 의미

 - 힙에 시작점 넣기

 - 힙이 False일때까지 다음의 작업을 반복

      - 힙의 최소값을 꺼내서, 해당 노드를 방문 안했다면

        방문표시, 해당 비용 추가, 연결된 간선을 힙에 넣어주기

 

4. 자료구조

  - 간선 저장되는 인접리스트 : [무게, 노드번호]

  - 힙 : [무게, 노드번호]

  - 방문여부 : bool[]

  - MST 결과값 : int

 

5. 시간복잡도 : O(ElogE) : 상세 설명은 동영상 참고 (참고동영상)

 

<필요 라이브러리>

heapq는 파이썬에서 **우선순위 큐(priority queue)**를 구현하기 위한 힙(Heap) 자료구조를 제공하는 모듈입니다. 힙은 이진 트리 기반의 자료구조로, 항상 부모 노드가 자식 노드보다 작은 값을 가지는 **최소 힙(min-heap)**을 기본으로 합니다. heapq는 이 최소 힙을 사용하여 요소를 효율적으로 정렬하거나 우선순위 큐 기능을 구현할 수 있습니다.

주요 함수

1. heapq.heappush(heap, item)
   힙에 새로운 요소를 추가합니다.
   • heap: 힙으로 사용할 리스트.
   • item: 추가할 요소.
   import heapq

   
   

   heap = []

   heapq.heappush(heap, 5)

   heapq.heappush(heap, 3)

   heapq.heappush(heap, 8)

   print(heap)  # [3, 5, 8]
2. heapq.heappop(heap)
   힙에서 가장 작은 요소를 제거하고 반환합니다.
   • heap: 힙으로 사용할 리스트.
   smallest = heapq.heappop(heap)

   print(smallest)  # 3

   print(heap)  # [5, 8]
3. heapq.heappushpop(heap, item)
   힙에 새로운 요소를 추가한 후, 가장 작은 요소를 제거하고 반환합니다.
   • heap: 힙으로 사용할 리스트.
   • item: 추가할 요소.
   smallest = heapq.heappushpop(heap, 1)

   print(smallest)  # 1

   print(heap)  # [5, 8]
4. heapq.heapreplace(heap, item)
   힙에서 가장 작은 요소를 제거하고, 새로운 요소로 대체합니다.
   • heap: 힙으로 사용할 리스트.
   • item: 대체할 요소.
   smallest = heapq.heapreplace(heap, 2)

   print(smallest)  # 5

   print(heap)  # [2, 8]
5. heapq.nlargest(n, iterable)
   이터러블에서 가장 큰 n개의 요소를 반환합니다.
   • n: 반환할 요소의 개수.
   • iterable: 순회할 대상.
   result = heapq.nlargest(2, [1, 3, 5, 7, 9])

   print(result)  # [9, 7]
6. heapq.nsmallest(n, iterable)
   이터러블에서 가장 작은 n개의 요소를 반환합니다.
   • n: 반환할 요소의 개수.
   • iterable: 순회할 대상.
   result = heapq.nsmallest(2, [1, 3, 5, 7, 9])

   print(result)  # [1, 3]

주요 특징

• heapq는 리스트를 힙으로 사용합니다.
• 최소 힙을 기본으로 제공하며, 이를 통해 작은 값부터 정렬됩니다.
• 시간 복잡도는 삽입과 삭제 모두 O(log n)입니다.

이 라이브러리는 우선순위가 중요한 작업에서 매우 유용하며, 특히 작업의 순서를 결정하는 알고리즘에서 자주 사용됩니다.