# kruskal

gwalgwal

🎄 최소 비용 신장 트리 (MST) 전체 그래프에서 총합이 최소인 신장 트리 신장 트리? 모든 정점을 연결 사이클이 존재하지 않는 부분 그래프 간선의 개수 : N -1 개 한 그래프에서 여러 개의 신장 트리가 나올 수 있다 MST? > Minimum Spanning Tree : 전체의 가중치 값 중 최소인 트리 Prim 알고리즘 > 하나의 정점에서 연결된 간선들 중에 하나씩 선택하며 MST를 만들어가는 방식 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지 트리 정점(tree vertices): MST를 만들기 위해 선택된 정점들 비트리 정점(nontree vertices): 선택되지 않은 정점들 우선순위 큐 - 힙 구현 prim 알고리즘 구현 Kruskal 알고리즘 > 모든 간선들 중 비용이 가장 적은 걸 우선으로 선택

uiwns811

최소 신장 트리 신장 트리 (Spanning Tree) : 그래프 내의 모든 정점을 포함하는 트리 모든 정점이 연결되어 있고, 사이클이 없는 그래프이다. 신장 트리는 n개의 정점을 (n-1)개의 간선으로 표현한다. 신장 트리 == 그래프의 최소 연결 부분 그래프 최소 신장 트리 (MST : Minimum Spanning Tree) : 간선들의 가중치의 합이 최소인 신장트리. 이미지 출처 위 그래프에서 오른쪽의 트리가 최소 신장 트리이다. 최소 신장트리가 되기 위한 조건 간선의 개수 = 정점의 개수 - 1 (정점 n, 간선 e일 때 e = n - 1 사이클이 없다. 3

jw3418

풀이 시간 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) 각 섬들마다 현

morion002

문제 문제 설명 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수

qzzloz

1. 신장 트리(Spanning Tree) 신장 트리: 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프 n-1개의 간선만 사용 2. 최소 비용 신장 트리(Minimum Spanning Tree, MST) 최소 비용 신장 트리(Minimum Spanning Tree, MST): 간선들의 가중치를 합한 값이 최소가 되는 신장 트리 n-1개의 간선만 사용한다. 사이클이 없다. 3. kruskal의 MST 알고리즘 greedy method: 각 단계에서 최선의 답을 선택하는 과정을 반복하는 알고리즘 설계 기법, 항상 최적의 해답을 주는지 검증이 필요하다. Kruskal의 MST 알고리즘은 최적의 해답임이 증명되었다. 그래프의 모든 **간선을 가중

morion002

Graph 최소 신장 트리 그래프의 정점과 간선 중 일부를 선택해서 구성하는 트리를 신장 트리라고 한다. 가중치 그래프일 때, 가장 적은 비용으로 모든 정점들을 연결하는 것이다. 최소 신장 트리는 순환하는 사이클 구조를 절대 가져서는 안 된다. Kruskal 노드의 개수가 n개일 때 간선을 가중치 기준으로 오름차순 정렬 가중치를 낮은 간선부터 선택 이때 간선으로 인해 사이클이 생기면 다음 간선 선택 선택한 간선이 n-1 개가 될 때까지 반복 코드로 구현하면 다음과 같다. Prim 하나의 정점에서 시작해서 정점을 하나씩 추가하는 알고리즘이다. 임의의 시작 정점을 선택 현재 선택된 정점들을 기준으로 인접한 정점 중 가

win-luck

10723번 판게아 1 문제 조금 독특한 요구사항이 있었던 MST 문제였다. 문제에서 추출할 수 있는 정보는 다음과 같다. 매번 도로가 추가될 때마다 모든 도시가 서로 직간접적으로 연결 선택된 도로들의 길이의 합이 최소여야 함(최소 스패닝 트리) 도로가 추가될 때마다 MST를 새로 형성해야 한다는 것만 캐치하면 해결할 수 있다. Kruskal 알고리즘으로 문제를 해결하였다. 테스트케이스 t, n과 m을 입력받은 뒤, 1 ~ n-1까지는 기존의

cldhfleks2

문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다. 출력 첫째 줄에 최소 스패닝 트리의 가중치를 출력한다. http

cldhfleks2

개요 여러 정점과 간선들로 이루어진 양방향 그래프가 있을때 부분 그래프가 최소한의 간선들로 이루어 졌을때 Spanning Tree, 신장트리라고 한다. 즉 Spanning Tree는 내부에 사이클이 없는 그래프를 의미하는것이다. 사이클이 생기는 순간 불필요한 간선이 하나 더 있는것이니까. 여기에서 모든 간선들의 가중치합이 최소가 될때 최소 신장 트리, Minimum Spanning Tree, MST라고 한다. 이러한 MST는 네트워크 라우팅, 통신망 설계등 실생활에서 자주 사용되는 개념이다. 작동원리 > 1. 최소 가중치의 간선들로만 이루어져야하므로, 가중치에대해 오름차순으로 정렬한다. 사이클이 형성되는순간 최소의 간선갯수(스패닝 트리 조건)에 위배 되므로 사이클이 형성되지 않도록 간선을 선택. 위 두 과정을 동시에 진행하면된다. 이때 2번과정은 DSU알고리즘의 일부인 find, union함수를 가져다가 쓸 것이다. (DSU알고리즘 >> https://velo

devkeon

최소 비용 트리 (Least Spanning Tree)를 공부하다가 풀게 된 문제이다. 이 문제에서 크루스칼 알고리즘을 사용하여 풀었다. 최소 비용 트리는 보통 프림 알고리즘이나 크루스칼 알고리즘을 사용하여 푼다. 그 중 크루스칼 알고리즘에 대해 먼저 다뤄보겠다. 크루스칼 알고리즘이란? 크루스칼 알고리즘을 이해하기 위해서는 그리디 알고리즘과 Union Find에 대해 알고 있어야 한다. 그리디 알고리즘이란? 우선 그리디 알고리즘에 대해 간단하게 설명하자면 당장 눈 앞에 있는 것들 중 최선의 것을 선택하며 나아가는 알고리즘이다. 당장 눈 앞에 있는 경우의 수에서 최선을 선택한다. 따라서 미래의 경우에는 고려하지 않는 알고리즘이다. 그림은 직접 그린 거라 조금 부족하다.. 그림에서

seg412

백준 6091 핑크 플로이드 풀이 주어진 예제를 기반으로 표를 인접 행렬을 표로 그려보면 | 입력 | 출력 | | :-: | :-: | | | <img src="https

u_u

MST (최소신장트리) Kruskal Prim 코드 아래 코드를 사용한 백준 문제풀이 백준 1197번 참고 블로그

morning-la

문제 도시 분할 계획 풀이 이번에 코테 보는데 내가 까먹은 알고리즘 나왔다. ...그것이 바로 최소 스패닝 트리 이제 보니 한번밖에 안풀었었음 (ㅎㅎ);; 순환이 없는 모든 정점을 연결해야 한다. 그러려면 간선의 부모가 같지 않으면 잇는다. 대신 비용이 가장 적은 도시 부터 이으면 된다 비용이 가장 적은 것부터 정렬하기 위해 클래스를 생성해준다 부모가 같은 것인지 판별한다 배열을 잇는다 구현 전체 코드 전체 코드

jnl1128

💬 문제 문제 난이도: 골드 4 문제 링크: https://www.acmicpc.net/problem/1647 문제 설명 한 마을에 N개의 집들이 있고, 그 집들을 연결하는 M개의 길이 있다. 각 길마다 길을 유지하는 유지비용이 있다. 이 마을을 두 마을로 분리하고 싶다. 이 때 각 마을에 있는 집들은 서로 연결되어 있어야 한다. 모든 길을 사용할 필요는 없다. 마을을 둘로 나누고 위의 조건을 만족할 때 드는 길의 유지비용의 최솟값을 출력하라. ❗️접근 방법 > ### MST 최소 스패닝 트리는 N개의 노드로 이루어진 연결 그래프에서 모든 노드를 연결하면서 사이클을 만들지 않는 스패닝 트리 중 간선의 가중치 합이 최소가 되는 트리이다. 가중치가 최소가 되고 사이클이 없어야 하므로 N개의 노드를 연결할 때 N-1개의 간선으로 연결되어 있다. 이 문제에서 모든 집을 연결하는 MST를 만든 후, 가장 가중치가 큰 간선 하나를 빼면 마을이 둘로 분리되

jnl1128

💬 문제 문제 난이도: 골드 4 문제 링크: https://www.acmicpc.net/problem/1976 문제 설명 도시들의 개수, 도시들 간 연결 여부가 주어진다. 그리고 도시를 여행할 순서가 주어졌을 때, 해당 순서로 도시를 여행할 수 있는지를 판별하라. 문제조건 a도시와 b도시가 연결되어 있다 == b도시와 a도시가 연결되어 있다. a->b로 여행을 갈 때, a와 b를 직접적으로 잇는 연결이 없더라도 다른 도시 c를 통해서 갈 수 있다면(a-c-b), 여행 갈 수 있다. 같은 도시를 여러 번 방문해도 된다. 도시의 개수는 200 이하이다. ❗️접근 방법 코드(Kruskal)

jnl1128

💬 문제 문제 난이도: Lv.3 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42861 문제 설명 n개의 섬 사이에 다리를 건설하는 비용이 주어진다. 모든 섬을 연결할 때 필요한 최소 비용을 바노한하라. 다리를 여러 번 건너서라도 도달할 수만 있다면 통행 가능한 경우이다. 가령 A섬과 C섬을 잇는 다리가 없더라도 B섬을 거쳐 갈 수 있다면 A섬과 C섬은 서로 통행 가능하다. 문제조건 연결할 수 없는 섬은 주어지지 않는다. A섬과 B섬을 잇는 비용이 C라면, B섬과 A섬을 잇는 비용도 C이다.(무방향) 섬의 개수는 1~100개이다. 간선의 개수는 ((n-1) * n)/2 이하이다. ❗️접근 방법 > ### Spanning Tree 스패닝 트리란 무방향 그래프에서 모든 노드가 연결되어 있는 트리이다. 보통 그래프는 여러 개의 스패닝 트리를 갖지만,

leverest96

Disjoint sets Disjoint sets(서로소 집합) : MST를 위한 기본 지식 서로 중복 포함된 원소가 없는 집합들 즉, 교집합이 없다. 집합에 속한 하나의 특정 멤버(대표자 / representative)를 통해 각 집합들을 구분 표현하는 방법 연결 리스트 트리 연산 + Pseudo Code Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산 Find-Set(x) : x를 포함하는 집합을 찾는 연산 Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산 연산의 효율을 높이는 방법 Rank를 이용한 Union 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크라는 이름으로 저장

olee11

알고리즘 개요 크루스칼 알고리즘이란? 크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘 중 하나입니다. 이 알고리즘은 그리디 알고리즘의 일종으로, 간선을 가중치의 오름차순으로 정렬한 뒤 작은 가중치부터 하나씩 선택해 최소 신장 트리를 구합니다. >최소 신장 트리(Minimum Spanning Tree, MST): 모든 정점을 포함하면서, 사이클을 형성하지 않으면서 그래프 상의 간선들의 가중치 합이 최소인 트리 알고리즘 동작 과정 알고리즘 구현 방법 그래프 구성 그래프를 이루는 모든

codesver

Link | 1647번 문제 : 도시 분할 계획 📌 About 문제에서 요구하는 것은 두 구역으로 쪼갠 마을의 최소 유지 비용을 구하는 것이다. 여기서 MST를 구하면 된다는 것을 떠올릴 수 있다. 간단히 kruskal algorithm을 사용하면 된다. 다만, 이 때 두 구역은 연결이 되어 있지 않는다. 즉, 간선의 개수는 집의 개수 - 2이며 MST에서 최대 비용 간선만 제거하면 된다. Kruskal algorithm에서는 최소 비용 간선부터 탐색한다. 그렇기 때문에 추가한 간선의 개수가 집의 개수 - 2가 될 때까지만 탐색을 하면 된다. Kruskal Algorithm...? 📌 Solution **📍 Step 0.

codesver

Link | 1197번 문제 : 최소 스패닝 트리 📌 About Graph에서 MST를 구하면 되는 문제로 Kruskal algorithm을 사용하면 된다. Kruskal algorithm에 대한 설명은 다음을 참고하면 된다. Floyd Warshall Algorithm Note 📌 Code [GitHub Repository](https://github.com/codesver/problem-solving-hub/tree/main/%EB%B0%B1%EC%A4%80/Gold/1197.%E2%80%85%EC%B5%9C%EC%86%8C%E2%80%85%EC%8A%A4%ED%8C%A8%EB%8B%9D%E2%80%85%ED%8A%B8%EB%A6%A