본문 바로가기

최소 버텍스 커버

BOJ)10276 Jewelry Exhibition 문제: icpc.me/10276 각 행이나 열에 빛을 발사해서 보석들을 지킬 때 모든 보석들을 지키는 최소한의 빛의 수를 구하는 문제이다. x행 y열의 위치에 존재하는 보석을 x정점과 y정점을 잇는 간선이라고 생각한다면 결국 모든 보석을 지키는건 각 행(정점)들을 몇개 선택하여 모든 간선을 커버하는 문제로 치환되므로 최소 버텍스 커버 문제로 볼 수 있다. 이분 그래프에서의 최소 버텍스 커버 문제는 쾨닉의 정리에 의해 이분 매칭으로 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include using namespace std;int t, n, m,.. 더보기
BOJ)1444 숌 언어 문제:icpc.me/1444 대문자와 소문자가 번갈아 나타나는 문장이 주어질 때 대문자와 소문자로 이루어진 최소 몇개의 단어로 문장을 만들 수 있는지를 출력하는 문제이다. 이 문제는 (대문자,소문자)로 이루어진 단어와 (소문자,대문자)로 이루어진 단어의 이분 그래프로 나타내면 최소 버텍스 커버 문제로 치환하여 해결할 수 있다. 예를들어 AaAbBa라는 단어가 있을 때 Ab라는 정점과 bB라는 정점이 연결되고 bB라는 정점과 Ba라는 정점이 연결될 것이다. 이 연결을 할 수 있게 만드는 정점의 최소수를 구하는 문제이기 때문에 최소 버텍스 커버 문제로 해결 가능한 것이다. 하지만 맨 처음 나오는 Aa라는 단어와 Ba라는 단어는 항상 선택이 강제 되어야하므로 해당 단어와 연결 된 간선들을 모두 제거해준 뒤 그.. 더보기
BOJ)1867 돌멩이 제거 문제: icpc.me/1867 한 행을 쭉 이동하거나 한 열을 쭉 이동하면서 돌멩이를 치울 때 최소의 이동횟수로 돌멩이를 다 치울 수 있는지 구하는 문제이다. 우리는 x행 y열에 놓인 돌멩이를 x와 y를 연결시켜주는 이분 그래프 형태로 만들어준 뒤 돌멩이를 줍는다는 것은 결국 x와 y를 연결시키는 간선을 포함하는 것이다. 즉 우리는 간선들을 전부 포함시키는 최소한의 정점을 구하면 된다. 즉 최소 버텍스 커버를 구하는 문제로 해석된다. 이분 그래프에서의 최소 버텍스 커버문제는 이분 매칭과 동치이므로 최대매칭을 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #.. 더보기