4Legs_Archives

문제 링크 : www.acmicpc.net/problem/16950 16950번: 레드 블루 스패닝 트리 2 첫 줄에는 세 정수 n, m, k가 주어진다. n은 그래프의 정점의 개수 (2 ≤ n ≤ 1,000)이고, m은 간선의 개수, k는 문제에 설명되어 있는 파란색 간선의 개수 (0 ≤ k < n) 이다. 다음 m개 줄에는 간선의 정 www.acmicpc.net [먼저 풀면 좋은 문제] [MST] BOJ 4792 레드 블루 스패닝 트리 문제 링크 : www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 4legs-study.tistory.com..

문제 링크 : www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 다음과 같은 그래프에서, 파란색 간선을 최소로 사용하는 스패닝 트리를 찾아보자. 파란색 간선을 최소로 사용했을 때의 스패닝 트리이다. 이는 곧, 예시 그래프에서 스패닝 트리를 구성하기 위해서는 최소 2개의 파란색 간선이 필요하다는 것을 의미한다. 즉 5-7, 6-8의 파란색 간선을 사용하지 않고서는 예시 그래프의 스패닝 트리를 구성할 수 없다. 그렇다면 마찬가지로 이번에는 파란색 간선을 최..

문제 링크 : www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 모든 도시에 전기가 공급되어야 하며, 한 도시가 둘 이상의 발전소에서 전기를 공급받지 않아야 한다는 점에서 MST를 구하는 문제로 접근할 수 있다. 둘 이상의 발전소에서 전기를 공급받지 않아야 한다는 것은 곧 사이클 없이 모든 정점을 잇는 것과 같기 때문이다. 단, 일반적인 MST 문제와의 차이는 아래의 예제와 같이 모든 정점이 서로 연결되어 있지는 않다..

최소 스패닝 트리에 대한 내용과 크루스칼 알고리즘은 아래 포스팅에서 확인할 수 있다. 최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm) 최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽 4legs-study.tistory.com 프림 알고리즘 (Prim Algorithm) 프림 알고리즘은 최소 스패닝 트리(MST)를 구하는 알고리즘으로, 다음과 같이 동작한다. ① 최초 출발 노드와 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해 MST에 추가한다. 이제 MST에는 2개의 정점이 포함되어..

최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 이번 ..