# 최소신장트리
[4386] 별자리 만들기
https://www.acmicpc.net/problem/4386 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 ...
[알고리즘] 최소 신장 트리 (Minimum Spanning Tree)
그래프 내의 모든 정점들을 포함하는 그래프의 부분집합(subgraph) Tree최소한의 간선들로 그래프 내의 모든 정점을 포함 \- 따라서 Spanning Tree는 cycle을 포함하지 않음 \- 그래프 내의 정점의 수가 n개이면, Spanning Tree는 (n
[백준 #1197]: 최소 스패닝 트리(python)
백준#1197:최소 스패닝 트리 >해당 문제는 최소 신장트리를 크루스칼 알고리즘을 이용하여 구현하여 해결하였다.
[ 백준 / Python3 ][골드3] 14950 - 정복자
https://www.acmicpc.net/problem/14950문제에는 어렵게 적어놓았지만 최소신장트리 문제였다.1번도시부터 시작해서 짧은 순으로 간다고 하였고 결국 모든 도시를 이어주는 것이 목표이므로 최소신장트리를 만들어주면 조건에 부합된다.roads에
[ 백준 / Python3 ][골드4] 1197 - 최소 스패닝 트리
https://www.acmicpc.net/board/view/108031제목부터 그러하듯 최소신장트리로 해결하는 문제이다.두 노드와 가중치를 한 배열에 저장하여 그 배열들을 모은 이차원 배열을 만든다.1번에서 저장한 배열을 가중치를 기준으로 오름차순으로 정렬
그래프 이론
알고리즘을 잊은 미래의 나를 이해시키기 위함핵심: 사이클이 존재한다? --> 부모 노드가 같은 노드끼리 합집합 연산을 할 때 발생한다.사용이유: 주어진 무방향 그래프의 사이클 존재여부를 판단하기 위함핵심: 두 노드를 합친다.원리: 두 노드를 합치고 부모 노드를 통일한다
백준 17472 다리 만들기 2
17472번: 다리 만들기 2 (acmicpc.net)섬의 개수와 위치 체크 BFS를 통해 이어지는 곳들을 모두 같은 섬으로 표시하고 BFS를 한 횟수만큼 섬이 있다고 보면 된다.다리 찾기N, M의 크기 제한이 크지 않기 때문에 2차원 배열을 완전 탐색하며 해당 위치
크루스칼 알고리즘 - 최소 신장 트리
그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않아야 함신장트리는 모든 노드가 연결되어 있지만 일부 간선을 사용하지 않아도 괜찮다.최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게
백준 1774. 우주신과의 교감 (파이썬- 최소신장트리, 크루스칼)
최소신장트리를 구하는 문제로 최소의 비용으로 우주신을 연결시키면된다.단, 이 문제의 포인트이자 다른 문제와의 차이점은 문제에서 일부 간선 edge가 주어진다.다시말해 일반적으로 최소 신장 트리문제는 크루스칼을 이용해서 최소의 비용의 합계를 구하면된다.여기서는 최소가 아
