[C/C++] 백준 열혈강호 문제 모음 / 백준 11375번, 백준 11376번, 백준 11377번

✏️ 문제 링크

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

11375번: 열혈강호

 

✏️ 문제 설명

 

✏️ 문제 풀이

기본적인 이분 매칭 구현 문제입니다.

이분 매칭이 먼지 잘 모르시겠다면?

https://pooreumjung.tistory.com/338

Algorithm 공부 #26 - 이분 매칭(Binary Matching)

 

✏️ 문제 코드

#include<iostream>
#include<vector>
using namespace std;
#define MAX 1001
int N, M;

vector<int> arr[MAX]; // 각 그룹의 정보를 저장할 배열
int d[MAX]; // 각 번호에 출발지를 저장할 배열
bool visit[MAX]; // 방문할 수 있는지를 체크할 배열
bool dfs(int node); // 매칭이 가능하면 true를, 불가능하면 false를 return
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		int work;
		cin >> work;
		while (work--) {
			int number;
			cin >> number;
			arr[i].push_back(number);
		}
	}

	int count = 0;
	for (int i = 1; i <= N; i++) {
		fill(visit, visit + MAX, false);
		if (dfs(i))
			count++;
	}
	cout << count;
}

bool dfs(int node)
{
	// 연결된 모든 노드에 대해서 들어갈 수 있는지 탐색
	for (int i = 0; i < arr[node].size(); i++) {
		int end = arr[node][i]; // 가려고자 하는 목적지
		if (visit[end]) // 이미 처리가 되었다면 pass
			continue;
		visit[end] = true; 
		if (d[end] == 0 || dfs(d[end])) {
			d[end] = node;
			return true;
		}
	}
	return false;
}

 

 

 

 

✏️ 문제 링크

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

11376번: 열혈강호 2

 

✏️ 문제 설명

 

✏️ 문제 풀이

위에서 풀었던 11375번과 비슷하나 x그룹에서 y그룹으로 한 정점에서 2개의 간선을 갈 수 있다는 점

이를 해결하기 위해서는 X그룹의 각 정점들에 대하여 DFS를 두 번씩 돌려주시면 됩니다.

그리고 돌릴 때마다 vist배열을 초기화해야 합니다.(안 해서 틀렸습니다를 받아버림...)

 

✏️ 문제 코드

#include<iostream>
#include<vector>
using namespace std;
#define MAX 1001
int N, M;

vector<int> arr[MAX]; // 각 그룹의 정보를 저장할 배열
int d[MAX]; // 각 번호에 출발지를 저장할 배열
bool visit[MAX]; // 방문할 수 있는지를 체크할 배열
bool dfs(int node); // 매칭이 가능하면 true를, 불가능하면 false를 return
int workCount[MAX];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		int work;
		cin >> work;
		workCount[i] = work;
		while (work--) {
			int number;
			cin >> number;
			arr[i].push_back(number);			
		}
	}

	int count = 0;
	for (int i = 1; i <= N; i++) {	
		for (int j = 0; j < 2; j++) {
			fill(visit, visit + MAX, false);
			if (dfs(i))
				count++;
		}
	}

	cout << count;
}

bool dfs(int node)
{
	// 연결된 모든 노드에 대해서 들어갈 수 있는지 탐색
	for (int i = 0; i < arr[node].size(); i++) {
		int end = arr[node][i]; // 가려고자 하는 목적지
		if (visit[end]) // 이미 처리가 되었다면 pass
			continue;
		visit[end] = true; 
		if (d[end] == 0 || dfs(d[end])) {
			d[end] = node;
			return true;
		}
	}
	return false;
}

 

 

 

✏️ 문제 링크

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

11377번: 열혈강호 3

 

 

✏️ 문제 설명

 

✏️ 문제 풀이

위의 문제들과 비슷하고 먼저 할 수 있는 일을 1개로 해서 매칭을 한 뒤

마지막에 2번의 일을 할 수 있도록 추가하면 됩니다

 

✏️ 문제 코드

#include<iostream>
#include<vector>
using namespace std;
int N, M, K;
vector<int>v[1001];
bool visit[1001];
int work[1001];
bool dfs(int node);
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M >> K;
	int num, wo,res=0,k=0;
	for (int i = 1; i <= N; i++) {
		cin >> num;
		for (int j = 0; j < num; j++) {
			cin >> wo;
			v[i].push_back(wo);
		}
	}
	for (int i = 1; i <= N; i++) {
		fill(visit, visit + 1001, false);
		if (dfs(i)) res++;
	}
	for (int i = 1; i <= N; i++) {
		fill(visit, visit + 1001, false);
		if (dfs(i)) {
			res++;
			k++;
		}
		if (k == K) break;
	}
	cout << res;
}

bool dfs(int node) {
	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];
		if (visit[next])continue;
		visit[next] = true;
		if (work[next] == 0 || dfs(work[next])) {
			work[next] = node;
			return true;
		}
	}
	return false;
}