boj,백준) 11376. 열혈강호2 (C / C++)

1. 문제 링크

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

11376번: 열혈강호 2

2. 문제 개요

 직원이 N명 있고 1~N번으로 번호가 매겨져 있다. 일은 1번부터 M번까지 번호가 매겨져 있다.

이때, 각 직원은 최대 두 개의 일을 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램 구현.

 

3. 문제 힌트

   이분 탐색 알고리즘을 알고 있다고 가정,

   DFS를 1번 실행할 때, DFS가 무엇을 의미하는 것인지 잘 생각해보기.

 

4. 문제 풀이

'열혈강호' https://kibbomi.tistory.com/41

boj) 11375. 열혈강호 (C / C++)

와 다른 점은 각 사람이 1개의 일을 할 수 있는데, 최대 2개의 일을 할 수 있게 변경되었다는 점이다.

x번 사람이 DFS를 1번 실행하여 반환되는 값 (TRUE / FALSE)은 TRUE = 할 일이 있음. FALSE = 할 일이 없음. 을 나타낸다.

 

이 문제에서 고려할 점은 특정한 사람이 2개의 일을 해야만 하는 것이 아닌 누가 됐든 간에 최대의 일을 하도록 매칭 해주면 된다는 점이다.

그래서 각 사람마다 DFS를 2번 실행시켜 최대 2개씩 매칭 해주도록 하였다.

 

5. 코드

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

int n, m;
vector<int> v[1001];	//use 1~n index
bool visited[1001] = { false, };
int matched[1001]; 

bool dfs(int cur)
{
	if (visited[cur])
		return false;

	visited[cur] = true;

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

	for (int i = 0; i < len; ++i)
	{
		int next = v[cur][i];

		if (matched[next] == 0 || dfs(matched[next]))
		{
			matched[next] = cur;
			return true;
		}
	}
	return false;
}

int main()
{
	int ans = 0;

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; ++i)
	{
		int count;
		scanf("%d", &count);

		for (int j = 0; j < count; ++j)
		{
			int to;
			scanf("%d", &to);

			v[i].push_back(to);
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			fill(visited, visited + 1001, false);
			if (dfs(i))
				ans++;
		}
	}
	printf("%d", ans);
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~