4Legs_Archives

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

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