MST

크루스칼 알고리즘(kruskal)

📔 크루스칼(kruskal) 이란 간선을 하나씩 선택해서 MST를 찾는 알고리즘 ( 프림은 정점을 선택, 크루스칼은 간선을 선택 ) 최초 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다 사이클이 존재하면 패쓰 ( 사이클의 존재를 파악하는게 중요! ) V-1개의 간선이 선택될 때 까지 반복 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 disjoint-set 알고리즘을 이용한다. 📔 크루스칼(kruskal) 구현 def make_set(x): p[x] = x def find_set(x): if p[x] == x: return x else: p[x] = find_set(p[x]) return p[x] def union(x, y): px ..

최소 신장 트리(Minimum Spanning Tree)

그래프에서 최소 비용을 구하는 문제 1. 모든 정점을 연결하는 간선들의 가중치합이 최소가 되는 트리 - 프림과 크루스칼 두가지 형태가 있다. (프림은 정점을 기준으로, 크루스칼은 간선을 기준으로 MST를 만들어간다.) 2. 두 정점 사이의 최소 비용 경로 찾기 - BFS에서 가중치가 추가된 형태 신장 트리 1. n 개의 정점으로 이루어진 무방향 그래프에서 n 개의 정점과 n-1 개의 간선으로 이루어진 트리 최소 신장 트리 1. 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 그래프의 표현 1. 인접 행렬 2. 인접 리스트 🟨 프림 알고리즘: 프림 알고리즘은 하나의 정점에 연결된 간선중 가중치가 최소인 정점을 선택한다. 하나의 정점에서 연결된 간선들 중에 하나씩 선택..

[python] SWEA - 1251. [S/W 문제해결 응용] 4일차 - 하나로

🤔문제 해결 1. D4 | MST - prim 2. 간선의 가중치를 값으로 하는 인접 행렬을 만든다 3. 최소 값을 갱신해줄 가중치 리스트, MST에 포함되지 체크하는 리스트, 부모노드 선택리스트를 만든다. (여기서는 모든 노드가 연결될 수 있기 때문에 부모노드는 필요하지 않을 수 있음) 4. 시작점을 선택(여기서는 0)하고 간선을 돌며 탐색한다 (1) 아직 MST에 포함되어 있지 않고, 가중치가 최소인 정점 u를 찾는다. (2) u를 MST에 포함시키고, 그 가중치를 결과값에 더해준다. (3) 가중치를 최솟값으로 갱신하기 위해 u에 인접하고 아직 mst가 아닌 정점(w) 중에서 key[w] > u-w 이면 갱신한다 5. 모든 노드를 선택할 때까지 4번을 반복한다. 💨 최소신장트리 알고리즘, 크루스칼과 ..

[python] 백준 - 1922. 네트워크 연결

문제 해결 1. 오늘 배운 최소 신장 트리(MST)를 사용하는 그래프 문제다. ( + heapq 모듈 사용 ) 💨 그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다. (1) 먼저 간선과 가중치를 인접리스트로 만든다. (2) key, mst, pq | 최소 가중치를 갱신하는 배열, 방문 배열, 힙큐( 최소값을 뽑는 모듈 ) 2. 시작점( 노드중 아무거나 )을 힙큐에 넣어주고 시작 - 이 문제에서는 모든 노드를 연결할 수 있다. (1) 힙큐 안에서 가중치가 가장 낮은 정점을 pop (2) 방문했는지 확인 | 이미 방문을 했다면 continue 를 통해 힙큐에서 다시 뽑고, 아니라면 True로 바꿔주고 가중치를 결과에 더해준다...