boj, 백준) 2051. 최소 버텍스 커버 ( C / C++)

1. 문제 링크

https://www.acmicpc.net/problem/2051

2051번: 최소 버텍스 커버

2. 문제 개요

이분 그래프의 최소 버텍스 커버(Minimum Vertex Cover)를 구하는 프로그램을 작성하시오. 단, 어떤 Node들이 Vertec cover를 구성하는지 출력할 것.

 

3. 문제 힌트

쾨닉의 정리에 의해서 최소 버텍스 커버 C의 개수는 이분 매칭의 최대 매칭 값 M과 같다.

어떤 노드들이 버텍스 커버C를 구성하는지 구하는 방법은 

C = (L - X) U (R ∩ X)

로 나타낼 수 있다. (증명은 글의 마지막에 링크를 달아두었습니다.)

L과 R은 이분그래프의 두 가지 집합, X는 매칭 되지 않은 정점 L로부터 출발하여 그 정점으로부터 Alternating path를 통해 도달할 수 있는 L, R의 모든 정점을 의미한다. 다시 말해서 Alternating path를 구하는데 지나치는 모든 정점이라고 보면 되겠다.

 

Alternating path에 대해서는 

youtu.be/C09tLeawgs0

이 영상에서 간단히 설명해준다.

 

정말 간단하게 말하면 L->R로 갈 때는 Matching에 사용 안 된 간선을 타고, R->L로 갈때는 Matching에 사용된 간선을 타고 갈 수 있는 경로를 나타낸다.

 

4. 문제 풀이

우선 버텍스 커버의 최소 개수를 구해야 한다. 이것은 이분 매칭의 최댓값과 같다는 것이 쾨닉의 정리에 의해서 증명이 되었다.

그럼 일단, 버텍스 커버의 최소 개수는 이분 매칭으로 구해주자.

 

자 그럼 이제 어떤 노드들로 버텍스 커버를 이루는지 구해야 한다.

 

alternating path를 구하는 건 BFS를 이용해서 만들었다.

어떤 하나의 왼쪽 그룹의 노드로부터 시작하여 Alternating path를 구할 때, L->R로 가는 경우는 여러 경로가 나올 수 있다. 그런데 R->L로 갈 때는 매칭에 사용된 간선 즉, 어떠한 간선 1개 만을 사용하므로, 이분 매칭 할 때, L의 어떤 정점 n에서 매칭 된 R의 정점을 기억해둬서 그 R의 정점으로는 가지 않도록 하고, R의 정점은 어떤 L의 정점으로부터 연결되었는지 체크하여 BFS 할 때 L-> R -> L로 탐색하지 않고 바로 L -> L로 탐색할 수 있도록 했다. 지나치는 노드마다 정점을 체크해서 3번에서 이야기했던 정의에 따라 L에서는 제외, R에는 추가하는 형식으로 해주었다.

 

문제의 첫 번째 예제와 답은 다르지만 정답이다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n, m, ans;
vector<vector<int>> adj;
vector<bool> visited, coverA, coverB;
vector<int> matchx, match;

void bfs(int now)
{
	queue<int>q;
	
	q.push(now);
	visited[now] = true;
	coverA[now] = false;

	while (!q.empty()) {
		int cur = q.front(); q.pop();

		coverA[cur] = false;

		int len = adj[cur].size();
		for (int i = 0; i < len; ++i) {
			int to = adj[cur][i];

			if (visited[matchx[to]])	continue;

			if (match[cur] != to && matchx[to] != -1) {	
				q.push(matchx[to]);
				visited[matchx[to]] = true;
				coverB[to] = true;
			}
		}
	}
	return;
}
bool dfs(int cur)
{
	visited[cur] = true;

	int len = adj[cur].size();

	for (int i = 0; i < len; ++i) {
		int to = adj[cur][i];

		if (matchx[to] == -1 || (!visited[matchx[to]] && dfs(matchx[to]))){
			matchx[to] = cur;
			match[cur] = to;
			return true;
		}
	}
	return false;
}


int main()
{
	scanf("%d %d", &n, &m);

	adj.resize(n + 1);
	visited.resize(n + 1);
	matchx.resize(m + 1, -1);
	match.resize(n + 1, -1);

	for (int i = 1; i <= n; ++i) {
		int k;
		scanf("%d", &k);
		for (int j = 0; j < k; ++j) {
			int to;
			scanf("%d", &to);
			adj[i].push_back(to);
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		fill(visited.begin(), visited.end(), false);
		if (dfs(i))
			ans++;
	}

	printf("%d\n",ans);

	coverA.resize(n + 1, true);
	coverB.resize(m + 1, false);
	fill(visited.begin(), visited.end(), false);

	for (int i = 1; i <= n; ++i) {
		//find X
		if (match[i] == -1 && !visited[i])
			bfs(i);
	}
	int na = 0, nb = 0;

	for (int i = 1; i <= n; ++i) 
		if (coverA[i])
			na++;
	
	for (int i = 1; i <= m; ++i)
		if (coverB[i])
			nb++;

	printf("%d", na);

	for (int i = 1; i <= n; ++i)
		if (coverA[i])
			printf(" %d", i);

	printf("\n%d", nb);

	for (int i = 1; i <= m; ++i)
		if (coverB[i])
			printf(" %d", i);
			
	return 0;
}

BFS 할 때 바로 체크해도 되는데 그냥 마지막에 반복문을 2번 돌려서 출력했다.

 

6. 결과

더 빠른 이분 매칭 알고리즘을 사용하면 시간을 단축할 수 있을 것 같다.

 

지적 질문 환영입니다~

 

 

증명 첨부

https://blog.naver.com/kks227/220967185015