# MST
최소 스패닝 트리 [BOJ1197]
가중치 무향 그래프가 있을때, 해당 그래프의 모든 노드를 연결하는 최소한의 가중치 합의 트리를 구하시오.각 가중치는 음수일 수 있고 1,000,000 이내의 절댓값을 가진다. 노드는 1만개 이하 간선은 10만개 이하다.
[알고리즘] 최소 스패닝 트리
Minimum Spanning Tree >- 가중 그래프의 총 간선 무게가 최소인 신장 트리 신장 트리: 그래프의 모든 정점을 포함하는 부그래프 중 트리인 것 Prim-Jarnik MST > 임의의 정점 S에서 시작하여 정점에 연결된 간선들 중 최소 가중치의 간선을
백준 2887
3차원 좌표 노드 (x, y, z) N개가 주어질때, 모든 노드를 최소 비용으로 연결시켜라.비용은 min(|x1 - x2|, |y1 - y2|, |z1 - z2|) 이다.모든 노드를 최소비용으로 연결하는 Minimum Spanning Tree를 만드는 문제이다.MST를
[백준] 4386 별자리 만들기
4386 별자리 만들기처음에 이 문제를 접했을 때 거리를 어떻게 구하더라... 까먹었었다.공식은 피타고라스의 정리를 이용하여 아래와 같다.최소 스패닝 트리 이 문제와 다르게 거리를 안주어져서 거리값만 구해서 넣어주면 된다.
[백준] 1197 최소 스패닝 트리
1197 최소 스패닝 트리이 문제는 MST를 공부해야 풀 수 있다.처음에 MST를 모르고 문제만 봤을 때 플로이드와샬 알고리즘인줄 알았는데 아니였다.플로이드 와샬은 하나의 정점에서 모든 정점으로 가는 최솟값을 구하는 것이고MST(최소 스패닝 트리)는 간선에 가중치를 고
백준 1647 '도시 분할 계획'
MST는 $N-1$개의 간선을 가져야 한다.만약 여기서 하나의 간선이 끊어질 경우, 그래프가 두 개의 연결그래프로 나뉜다.따라서 기존 MST와 달리 $N-2$개의 간선을 짧은 순서대로 연결한다.Kruskal을 사용하자.메모리: 332564 KB시간: 1732 ms메모리
백준 23034 - 조별 과제 멈춰!
https://www.acmicpc.net/problem/23034크루스칼과 BFS를 활용하여 풀이할 수 있는 문제였다.먼저 T를 구하기 위해서 우선 주어진 모든 간선에서 MST를 구성하여모든 정점을 연결하는데 필요한 최소한의 간선만을 남겨야 한다.이를 위해
[백준] 1197 / 최소 스패닝 트리 (MST/프림)
문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와
백준 4386 별자리 만들기 (C++)
4386번: 별자리 만들기크루스칼 알고리즘을 이용한 문제이다. 먼저 입력받은 별들 간의 거리를 모두 구해 벡터에 저장해주고 거리를 기준으로 오름차순으로 졍렬을 해주었다. 그리고 크루스칼을 통해 루트를 바꿔주게 되는데 거리 순으로 정렬을 했으므로 가까운 거리부터 루트를
[알고리즘] 최소 신장 트리(MST)
최소 신장 트리란? 최소 신장 트리를 알아보기 전에 신장 트리를 알아보자 신장트리 : 어떤 그래프의 부분 그래프이면서 동시에 모든 정점을 포함하는 트리를 이르는 말 정점이 V개일 때 간선은 V-1개이며 트리이므로 사이클이 생겨서는 안된다는 특징이 있다. 최소 신
[BOJ/C++] 10423 전기가 부족해
https://www.acmicpc.net/problem/10423문제세계에서 GDP가 가장 높은 서강 나라는 소프트웨어와 하드웨어 기술이 모두 최고라서 IT강국이라 불리고, 2015년부터 세상에서 가장 살기 좋은 나라 1등으로 꼽히고 있다. 살기 좋은 나라
백준 17472 '다리 만들기 2'
맵 전체를 탐색하며 섬을 발견하면 사방 탐색으로 인접한 모든 섬 타일에 번호를 붙인다.DFS, BFS 중 DFS를 사용하였다.이 섬 번호는 그래프에서 정점 번호로 사용한다.맵 전체를 탐색하며 섬 타일이라면 4방향으로 다리를 뻗어본다.다리가 같은 섬에 이어진다면 취소한다
MST와 최단경로 정리
최소신장트리 : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치들의 합이 최소인 신장 트리정점의 개수가 N일때 N(N-1)/4 -> N^2/4를 기준으로 간선이 많다 적다를 판단한다간선이 적으면 Kruskal간선이 많으면 Prim간선중심으로 최소신장트리를
[백준] 1197번 : 최소 스패닝 트리
최소 스패닝 트리우선 기본 지식을 알아 보겠다.원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 함.(간선들이 사이클을 이루지 않아야 함.)주어진 그래프의 모든 정점들을 연결하는 부분 그