알고리즘 코딩테스트 핵심이론 강의 - 최소신장트리(MST)

https://www.youtube.com/watch?v=N9xLuHLMIN8&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=34

📌 최소신장트리(MST)

• 그래프에서 모든 노드를 연결 할 때 사용된 에지들의 가중치릐 합을 최소로 하는 트리
• 대표적인 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 있다.

 

◾ 최소신장트리(MST)의 특징

• 사이클이 포함되면 가중치의 합의 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다.
• 에지 리스트의 형태를 이용해 데이터를 담기 때문에 구현이 약간 까다롭다.
• 사이클이 존재하면 안되기 때문에 사이클 판별 알고리즘인 유니온 파인드알고리즘을 내부에 구현해야함.

1. 에지 리스트로 그래프 구현하고 유니온 파인드 리스트 초기화하기

• 에지 리스트를 그래프로 구현 → 그래프의 표현
  유니온 파인드 리스트 초기화 → 유니온 파인드
  사이클 판별을 위해서 사용

• 그래프 에지 리스트 : 최소 신장 트리는 데이터를 에지 중심으로 저장하므로 에지 리스트의 형태로 저장
• 유니온 파인드 리스트 : 리스트의 인덱스를 해당 자리의 값으로 초기화

 

2. 그래프 데이터를 가중치 기준으로 정렬하기

• 에지 리스트에 담긴 그래프를 데이터 가중치 기준으로 오름차순 정렬
  → 오름차순은 input 데이터의 순서 조정을 통해 높은 자유도로 정렬 가능

 

3. 가중치가 낮은 에지부터 연결 시도

• 가중치가 낮은 에지부터 연결 시도를 하되, 바로 연결하지 않고 에지를 연결 햇을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인 후 사이클이 형성되지 않을 때만 union 연산을 이용해 두 노드를 연결

 

• find를 통해 유니온 파인드 리스트에서 부모노드를 확인
• 현재 4의 부모 노드는 4, 5의 부모노드는 5 이므로 연결 (5에 들어있는 노드를 4로 변경

 

4. 3번을 반복

• 전체 노드 개수가 N개이면 연결한 에지의 개수가 N-1이 될 때까지 반복

 

 

 

• find(5)를 했을 때 대표 노드가 2로 바뀌는 이유 : find(5)를 했을 때 값은 4가 나온다.
  find 했을 때 자기와 값이 같은지 보고 다르면 해당 인덱스로 이동
  find 했을 때 5 != 4 이기 때문에 인덱스 4로 이동하여 대표 노드를 업데이트

 

• find(1) 했을 때 대표노드 1 , find(2) 했을 때 대표노드 2.
  두 대표 노드가 다르기 때문에 사이클이 생기지 않아 연결

 

5. 총 에지 비용 출력

• 전체 노드 개수가 N개이면 연결한 에지의 개수가 N-1이 될 때까지 반복

• 총 에지 비용 2 + 3 + 4 + 8 = 17