BOJ 백준온라인져지 11375 열혈강호 풀이

이분 매칭 문제를 엄청 오랜만에 풀어봤다.

https://en.wikipedia.org/wiki/Matching_(graph_theory)

http://koosaga.com/18

http://1ambda.github.io/algorithm/algorithm-part2-5/

위 링크에 많은 설명이 있고, 읽지는 않았다.

이 문제를 풀이한 방법은 아주 기초적인 DFS 를 이용한 O(V * E) 이다.

오늘은 시간이 없어서 이론보다는 구현을 목적으로 공부했다.

풀이 방법

1. 사람을 한명씩 dfs 로 연결할 수 있는 일을 잡는다.

2. 이미 연결돼있는 선이라면 그 선에 연결된 사람이 다른 일을 잡을 수 있는지 확인한다.

3. 반복

4. 끝

	#include <cstdio>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/11375
	* BOJ 백준온라인져지 11375 열혈강호 풀이
	*/
	using namespace std;
	vector<vector<int> > adj;
	vector<int> match;
	vector<bool> visited;
	int workCount;
	bool dfs (int here) {
	if (visited[here]) return false;
	visited[here] = true;
	for (int there = 1; there <= workCount; there++) {
	if (adj[here][there]) {
	if (match[there] == -1 || dfs(match[there])) {
	match[there] = here;
	return true;
	}
	}
	}
	return false;
	}
	int main () {
	int personCount;
	scanf("%d%d", &personCount, &workCount);
	adj.resize(personCount + 1);
	for (int i = 1; i <= personCount; i++) {
	adj[i].resize(workCount + 1);
	int length;
	scanf("%d", &length);
	for (int j = 0; j < length; j++) {
	int work;
	scanf("%d", &work);
	adj[i][work] = 1;
	}
	}
	int result = 0;
	match = vector<int>(workCount + 1, -1);
	for (int i = 1; i <= personCount; i++) {
	visited = vector<bool>(personCount + 1, false);
	if (dfs(i)) result++;
	}
	printf("%d", result);
	}

view raw BOJ_11375.cpp hosted with ❤ by GitHub