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

1. 문제 링크

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

11375번: 열혈강호

2. 문제 개요

 직원이 N명 있고 할 일이 M개가 있다. 각 직원이 할 수 있는 일의 번호가 주어졌을 때 최대 몇 개를 할 수 있는지 구하는 프로그램 작성.

 

3. 문제 힌트

 이분매칭 알고리즘을 알아야 한다.

 DFS로 구현하니 한번 생각해보자.

 

4. 문제 풀기

이분 매칭 알고리즘은 DFS로 구현한다.

직원 1명당 DFS를 1번씩 돌린다.

문제의 보기를 예로 들자면,

 

 

 

초기 상태로, 왼쪽은 사람 오른쪽은 일이다.

 

※ 사람이 할 수 있는 일은 인접 리스트로 구현하는 것이 좋다.

※ 각 일을 기준으로 누가 자신(일)을 맡았는지 저장하는 배열을 선언해둔다. (Size : 일의 개수)

 

(1) 첫 번째 탐색

 각 사람의 방문 여부를 나타내기 위한 Visited 배열을 사람 크기만큼 선언 후 방문 안 함으로 할당.

 1번 사람을 위한 DFS를 시작한다. 

 1번을 방문 처리하고,  1번 사람이 할 수 있는 일 (1, 2)를 순서대로 방문하는데, 만약 아무도 할당하지 않았다면 자신이 그 일을 맡고 DFS를 마친다.

 

 

첫번째 탐색 결과

 

(2) 두 번째 탐색

 또 각 사람의 방문 여부를 나타내기 위한 VIsited배열을 사람 크기만큼 선언 후 방문 안 함으로 할당한다.

 2번 사람을 위한 DFS를 시작한다.

 2번을 방문 처리하고,  첫 번째 탐색과 마찬가지로, 2번 사람이 할 수 있는 일 (1)을 방문한다.

 일 1번은 사람 1번에게 할당되어있다. 그럼, 1번 일을 2번에게 할당하고 1번이 다른 일을 하도록 해야 한다.

 그럼 사람 1번으로 와서 방문 처리를 하고, 할 수 있는 일  (1,2)를 방문한다.

 일 1번은 사람 2번이 맡고 있지만, 이미 방문했기 때문에 넘어간다.

 일 2번은 아무도 하고 있지 않기 때문에 2번 일을 자신이 맡고 DFS를 종료한다.

 ※ 여기서 만약에 사람 2번이 사람 1번의 일을 뺏고 1번이 다른 일을 찾지 못한다 해도 결괏값에는 변화가 없으므로 해도 상관없다.

두번째 탐색 결과

(3) 세 번째 탐색

 Visited배열 선언 위와 동일.

 3번 사람을 위한 DFS를 시작.

마찬가지로 사람 3번을 방문 처리하고 사람 3번이 할 수 있는 일 (2,3) 순서대로 방문한다.

일 2번을 사람 3번이 방문할 때, 사람 1번이 맡고있으므로 사람1번으로 들어간다.

사람1번이 할 수 있는 일(1,2) 중 일 1번을 방문할 때 사람 2번이 맡고 있으므로 사람2번으로 들어간다.

사람 2번이 할 수 있는일(1)중 1은 사람1번이 맡고있고 사람1번은 이미 방문했으므로 사람2번이 할 수있는 일은 없어진다.

따라서 2번의 일이 없어지고, 1번은 1번, 3번은 2번 일을 하게 된다.

세번째 탐색 결과

(4) 네 번째 탐색

위의 과정처럼 4번 사람은 3번 일을 맡게 된다.

네번째 탐색 결과

(5) 다섯 번째 탐색

위의 과정처럼 사람 5번은 일 1번을 방문한다.

일 1번은 사람 1번이 맡고 있으므로 사람 1번을 방문한다.

사람 1번은 일(1,2)을 순서대로 방문하는데, 일 1번은 사람 5번, 즉 이미 방문한 사람이므로 건너뛰고,

일 2번을 맡게 된다.

일 2번은 사람 3번이 맡고 있으므로 사람 3번으로 간다.

사람 3번은 일(2,3) 번을 방문하는데 일 2번은 사람 1번이 맡고 있고 이미 방문한 사람이므로 일 3번을 맡게 된다.

일 3번은 사람 4번이 맡고있고 사람4번이 할 수 있는 일 (3,4,5) 중에 4번을 선택하고 탐색이 종료된다.

 

다섯번째 탐색 결과

 

5. 코드

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

int n, m;
vector<int> v[1001];
bool visited[1001];
int work[1001];
int ret = 0;
bool dfs(int from)
{
	//if(visited[from]) return false;

	visited[from] = true;

	int len = v[from].size();
	for (int i = 0; i < len; i++)
	{
		int to = v[from][i];
        //if(work[to] == 0 ||dfs(work[to]))
		if (work[to] == 0 || !visited[work[to]] && dfs(work[to]))
		{
			work[to] = from;
			return true;
		}
	}
	return false;
}
int main(void)
{
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		int m;
		scanf("%d", &m);
		for (int j = 0;j< m; j++)
		{
			int can;
			scanf("%d", &can);
			v[i].push_back(can);
			
		}
	}
	for (int i = 1; i <= n; i++)
	{
		memset(visited, false, sizeof(visited));
		if (dfs(i))
			ret++;
	}
	printf("%d", ret);
	return 0;
}

주석처럼, 방문 결과 체크를 함수 실행 후 한 것과 실행전에 한것과 약 100ms의 차이가 있었다.

 

6. 결과 사진

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