# Minimum Spanning Tree
크루스칼 알고리즘
크루스칼 알고리즘 현재 간선들 중 가중치가 최소인 간선을 선택하는 그리디 알고리즘이다. 즉 최소 신장 트리(MST)를 만드는 대표적인 알고리즘이다. 간선들을 가중치가 낮은 순서대로 오름차순 정렬한다. 간선들을 확인해가며 싸이클이 형성되지 않는 간선들을 선택한다. (이 과정에서 Union Find 를 이용하여 싸이클 생성 여부를 파악한다.) 다음과 같은 그래프의 MSP를 구해보자. > union-find 를 이용하여 싸이클이 형성되는지 확인한다. 이미 같은 그룹에 속한다면 싸이클을 형성하는 것이다. 모든 간선 정보를 가중치를 기준으로 오름차순 정렬시킨다. 
17472: 다리 만들기 2
풀이 시간 1h 17m 알고리즘 분류를 보고 Minimum Spanning Tree와 Kruskal 알고리즘을 공부한 후에 풀었다 구현 방식 BFS와 MST를 찾는 Kruskal 알고리즘을 이용하여 풀었다 1) 일단 섬들을 구분지어주고, 2) 각 섬들마다 다른 섬들로 이동할 수 있는 최소 길이의 다리를 모두 구해주었다. 3) 간선(bridge)들을 모두 순회하면서 Kruskal 알고리즘을 이용해 MST를 찾아주었다. partition(x, y, color) boardx가 1인 지점마다 bfs를 순회하여 섬들마다 다른 숫자로 board에 표시해둠 bridge(x, y, color) 각 섬들마다 현
MINIMUM SPANNING TREE(MST)
기본개념 spanning tree: 그래프 내에 모든 정점을 포함하는 트리 mst: spanning tree 중 edge 가중치 합이 최소인 트리 여러개의 mst 가질 수 있음 KRUSKAL’S ALGORITHM greedy 알고리즘 간선의 가중치 오름차순 정렬 정렬된 간선들을 탐색하며 해당 간선을 신장 트리에 포함할 때 1. 사이클이 발생한 경우 신장 트리에 포함하지 않고 넘어감 사이클이 발생하지 않는 경우 신장 트리에 포함 모든 정점을 연결할 때까지 위 과정 반복 PRIM’S ALGORITHM greedy 알고리즘 O(v^2) 최초 출발 노드와 연결되어
[Python] 최소 신장 트리(MST, Minimum Spanning Tree)
정의 신장 트리 중 사용된 간선들의 가중치 합이 최소인 트리 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아님 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것 특징 간선의 가중치 합이 최소 N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선만을 사용 사이클이 존재해서는 안됨 🔗MST 구현 알고리즘 [Kruskal MST 알고리즘](https://velog.io/@dmsgur7112/Python-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
MST(Minimum Spanning Tree)
스패닝 트리 : 그래프에서 일부 간선을 선택해서 만든 트리 : 스패닝 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안됨 ( 트리의 정의가 사이클 없이 모든 정점이 연결되어 있는 그래프) : 스패닝 트리는 그래프에 있는 n개의 정점을 n-1개의 간선으로 연결 최소 스패닝 트리 : 그래프에서 tree를 만들 때, 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리 : n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용해야 함 : 사이클이 포함되어서는 안됨 : Prim 알고리즘과 Kruskal 알고리즘이 대표적임 (가장 중요한 것은 사이클을 만들지 않는다는 것) Prim, Kruskal 알고리즘 비교 : Prim 알고리즘 -> 시작점에서 끝점까지 단계적으로 확장, 정점 선택을 기준으로 최적해 찾기 : Kruskal 알고리즘 -> 가중치를 간선에 할당, 간선 선택을 기준으로 최적해 찾기 프림 알고리즘
[Data Structure & Algorithm] 최소 신장 트리 & 크루스칼 알고리즘 (shortest path)
Data Structure 신장 트리(Spanning Tree): Tree 자료구조 중 하나입니다 하나의 graph가 있을때 모든 node를 포함하면서 cycle이 존재하지 않는, 부분 graph를 뜻 합니다 최소 신장 트리(Minimum Spanning Tree, MST): 하나의 graph에서 여러개의 신장 트리가 나올 수 있는데, 이 중 최소한의 비용의 트리를 최소 신장 트리라 합니다 spanning tree Algorithm MST 를 찾는 알고리즘으로 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim’s algorithm)이 존재하는데 본 글에서는 크루스칼 알고리즘에 대해 알아 보겠습니다 크루스칼 알고리즘 특징: greedy algorith
[Python] 백준 16398 - 행성 연결 문제 풀이
Overview BOJ 16398번 행성 연결 Python 문제 풀이 분류: Minimum Spanning Tree (최소 스패닝 트리), Kruskal Algorithm (크루스칼 알고리즘) 문제 페이지 풀이 코드 크루스칼 알고리즘을 이용하여, 최소 신장 트리를 만들어 답을 구한다.
[Python] 백준 1647 - 도시 분할 계획 문제 풀이
Overview BOJ 1647번 도시 분할 계획 Python 문제 풀이 분류: Minimum Spanning Tree (최소 스패닝 트리), Kruskal Algorithm (크루스칼 알고리즘) 문제 페이지 풀이 코드 크루스칼 알고리즘을 이용하여, 두 개의 최소 신장 트리를 만드는 문제이다. 루트 노드(부모 노드)가 2개만 남을 때까지 최소 신장 트리를 만들며, 간선 비용을 더한다. 이 방법 말고도 하나의 최소 신장 트리를 완성한 뒤에, 마지막에 추가된 간선을 제거해도 동일한 결과가 나온다. 이 풀이에서 각 노드의 부모 값을 저장하는 parents는 list 자료형이 아닌 defaultdict 자료형을 이용하였다. 동일한 유형 문제에서 전체 크기를 엄청나게 늘려서 출제하는 경우, list가 아닌 해시나 이진트리를 활용하여 유니언 파인드 구조를 사용해야 하기 때문에 미
[알고리즘]Minimum Spanning Tree (MST) - 최소 신장 트리
프로그래머스 문제를 풀던 중 전혀 모르는 문제에 직면하게 되었다... 찾아보니 MST를 찾는 문제로 이를 해결하기 위한 알고리즘이 존재한다는 것과, 내가 이를 수업시간에 공부했었다는 것을 알게 되었다. 알고리즘 A+ 이었는데... 군대가 문제일까 내 머리가 문제일까.. 이번 기회에 알고리즘 문제만 풀게 아니라, 자료구조와 알고리즘을 한번 정리해보려한다. Minimum Spanning Tree MST는 연결마다 가중치가 있는 무방향 그래프에서 모든 노드를 최소의 비용으로 연결하는 방법에 대한 것입니다. 주로 제가 풀었던 문제처럼 섬을 연결하거나, 도시간의 도로 연결, 네트워크 연결 등 최소 비용으로 노드들을 연결해야하는 문제들은 대부분 Minimum Spanning Tree로 해결 가능하다고 생각하면 될 것 같습니다. 자세한 사항을 설명드리면, 아래와 같은 그래프가 있다고 가정하고 설명드리겠습니다. <img wid
<Data Structure> Spanning Tree
목표 Spanning Tree, Minimum Spanning Tree(MST)에 대한 개념과 만드는 방법을 알 수 있습니다. 수준 미리 선행해서 알아야 할 내용은 없습니다. Spanning Tree 💡 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree = 신장 트리 신장 : span을 그대로 번역한 한것으로, 한 노드에서 다른 모든 노드로 갈 수 있다는 의미로 보임 Tree : 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프 Graph : 꼭짓점과 변으로 이루어지는 구조 💡 Spanning Tree는 그래프의 최소 연결 부분 그래프이다. 최소연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로
무방향 그래프에서의 사이클여부 확인 방법
1. 서론 최근 "최소 스패닝 트리"에 대해 알게되고 해당 문제를 접하게 되었다. 당연히 그래프에서 사이클의 존재 여부를 파악하기 위해서는 DFS를 통해 전부 탐색해봐야지만 판단할 수 있다고 생각하고 있었다. 그러나 해당 포스트에서는 DFS보다 훨씬 간단하고, 적은 시간이 걸리는 서로소 집합을 통한 사이클 판별, 즉 부모 노드를 각 노드에 기록하는 방식으로 이를 해결하는 방법에 대해서 서술한다. "이 포스트는 동빈나유튜브 채널을 참고 하였으며, 해당 채널에서 설명한 코드를 설명합니다. 언젠가 글쓴이가 생각한 방식에 대해서도 서술할 예정입니다." 2. 본론 1. 아이디어 각 노드별로 부모노드를 저장해놓고, 모든 노드 거쳐가면서 갱신해준다. 처음 각 부모노드는 자기 자신을 가리키며, 추후 갱신을 통해 특정 노드의 소속이 된다. 첫 포스트여서 굉장히 추상적이긴 하지
백준 1197 | 최소 스패닝 트리 (최소 신장 트리-MST, 크루스칼 알고리즘)
문제 출처 : https://www.acmicpc.net/problem/1197 문제 정점의 개수 v 간선의 개수 e 정점 a, 정점 b, 가중치 c 가 주어질 때 주어진 그래프의 최소 스패닝 트리의 가중치를 구하시오. 문제 접근 방법 최소 신장 트리(MST, Minimum Spanning Tree)에 관한 문제이다. MST 문제를 푸는 방법에는 간선의 길이를 기준으로 최솟값부터 찾아가는 크루스칼 알고리즘 과 노드를 기준으로 작은 간선을 선택해나가는 프림 알고리즘 이 있다. 이 문제는 크루스칼 알고리즘과 그래프의 싸이클 체크를 위한 Union Find를 이용하여 풀 예정이다. 입력받은 간선의 가중치 기준으로 오름차순 정렬한다. 튜플 or 리스트 형태로 append( (가중치, a, b) ) 정렬된 리스트에서 두 정점에 대해 싸이클을 형성하는지를 Union Find를 통해 확인한
알고리즘 스터디 - 최소신장트리(MST) feat. Python
최소 신장 트리 (MST : Minimum Spanning Tree) 최소 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리를 지칭함 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아님 MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것 즉, 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것 MST의 특징 간선의
최소 신장(스패닝) 트리(minimum spanning tree)
Spanning Tree 우선, Spanning Tree는 무엇일까? > 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 간선의 수(edges)가 가장 적게, 최소 연결을 해야하는 트리 N개의 정점(Vertex)를 갖는 그래프 최소 간선의 수(Edges)는 N-1개 다시말하자면 그래프에서 일부 간선들로 이루어진 트리를 말한다 전체 그래프의 모습 일부 간선들로 이루어진 트리의 모습
[알고리즘] Prim's algorithm
최소 신장 트리 Spanning Tree(신장 트리)란 Cycle이 없지만 모든 node들이 연결되어있는 그래프를 의미한다. Spanning Tree가 되기 위한 조건은 Tree가 그래프의 모든 node들을 포함하며 Tree의 속성인 Cycle이 없음을 만족해야한다. 아래의 사진은 Spanning Tree의 예시를 나타낸 사진이다. Minimun Spanning Tree(MST, 최소 신장 트리)는 Spanning Tree중에서 Edge(간선)의 가중치의 합이 최소인 Spanning Tree를 의미한다. 대표적인 알고리즘으로는 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)이 있다. Prim's algorithm 프림 알고리즘은 시작 Nod
원더랜드(Prim)
원더랜드 원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다. 원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다. 입력 설명 첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다. 다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다. 출력 설명 모든 도시를 연결하면서 드는 최소비용을 출려한다. 입력 9 12
Minimum Spanning Tree(MST)
Spanning Tree Spanning Tree는 그래프 내 모든 정점을 포함하는 Tree를 말한다. 모든 정점을 연결하는 Path를 만드는 경우 사용되는 개념으로 N개의 정점이 존재할 경우 간선은 항상 N-1개이다.(Cycle 존재 X) Minimum Spanning Tree MST는 최소 신장 트리를 말하며 모든 edge의 weight 합이 최소인 트리를 말한다. 구현 방법에는 Kruskal 알고리즘과 Prim 알고리즘이 있다. Kruskal Algorithm Kruskal은 Greedy 알고리즘을 기반으로 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 알고리즘이다. 각 간선을 선택하는 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. [방식] 그래프들의 간선을 가중치 오름차순 정렬 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택 해당 간선을
원더랜드(Kruskal)
원더랜드 원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다. 원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다. 입력 설명 첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다. 다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다. 출력 설명 모든 도시를 연결하면서 드는 최소비용을 출려한다. 입력 9 12
최소신장트리
신장 트리 (Spanning Tree) 조건 : 그래프 G는 connected graph이다. 정의 : 그래프 G의 spanning tree는 다음 성질을 만족하는 G의 부분 그래프이다. G의 모든 정점들이 포함되어야 한다. connected 그래프이어야 한다. 사이클을 포함하지 않아야 한다. 신장트리는 다음 두 가지 방식으로도 구할 수 있다. DFS : DFS를 돌린 후 각 노드 v마다 (pred[v], v) 간선을 선택한다. BFS : BFS를 돌린 후 각 노드 v마다 (pred[v], v) 간선을 선택한다. 그래프 G의 신장트리 G'는 V(G') = V(G)이고 G'는 연결 되어있는 최소 부분 그래프(Minimal Subgraph)이다. 정점수 n인 그래프의 신장 트리는 n - 1개의 간선 가짐 **최소비용 신장트리(Minimal-cost S