백준 11375번

열혈강호

Posted by ChoiCube84 on August 22, 2023 · 9 mins read

백준 11375번

오늘 풀어본 문제는 백준의 11375번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 7

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

강호네 회사에는 직원이 NN 명이 있고, 해야할 일이 MM 개가 있다. 직원은 11 번부터 NN 번까지 번호가 매겨져 있고, 일은 11 번부터 MM 번까지 번호가 매겨져 있다.

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

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

입력

첫째 줄에 직원의 수 NN 과 일의 개수 MM 이 주어진다. (1N,M1,000)(1 \leq N, M \leq 1,000)

둘째 줄부터 NN 개의 줄의 ii 번째 줄에는 ii 번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

풀이과정

1번째 시도

이 문제는 ‘이분 매칭’ 문제이다. 이분 매칭이 무엇인지 간단하게 설명하자면, 이분 그래프에서 간선들이 한쪽 그룹에서 다른 그룹으로만 향하는 그래프의 최대 유량을 구하는 것이다.

문제를 읽어보면 알겠지만, 할 수 있는 일의 최대 개수를 알아야 하고, 직원과 일로 그룹을 나눌 수 있으며, 간선의 방향을 직원에서 일로 가도록 이분 그래프를 만들 수 있다. 여기서 최대 유량을 구하면 그게 곧 할 수 있는 일의 최대 개수가 되는 것이다.

문제를 풀기 위해서 Ford-Fulkerson, Edmond-Karp 알고리즘을 사용할 수도 있겠지만, 비교적 간단한 방법인 DFS를 이용하여 해결하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

bool visited[1002] = { 0, };

int assignedWork[1002] = { 0, };
int getWorker[1002] = { 0, };

vector<int> graph[1002];

bool match(int worker);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, answer = 0;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		int numberOfWorks;
		cin >> numberOfWorks;

		while (numberOfWorks--) {
			int workNumber;
			cin >> workNumber;
			
			graph[i].emplace_back(workNumber + N);
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int i = 1; i <= N; i++) {
			visited[i] = false;
		}
		answer += match(i);
	}

	cout << answer;

	return 0;
}

bool match(int worker) {
	if (visited[worker] == false) {
		visited[worker] = true;
		for (auto possibleWork : graph[worker]) {
			if (getWorker[possibleWork] == 0 || match(getWorker[possibleWork])) {
				assignedWork[worker] = possibleWork;
				getWorker[possibleWork] = worker;
				return 1;
			}
		}
	}
	return 0;
}

실행 결과 ‘런타임 에러 (OutOfBounds)’ 가 발생하였다.

2번째 시도

이런 문제가 발생한 이유는 처음에 그래프를 설정하는 과정에서 정점의 개수의 최댓값을 N+MN + M 의 최댓값이 아니라 NN의 최대값으로 설정했기 때문이다.

각 배열에서 정점의 개수의 최댓값을 바꿔줄 수도 있었겠지만, 정점의 번호가 겹쳐도 간선의 방향이 다른 그룹으로만 향하기 때문에 문제가 발생하지 않을 것이라고 생각하여 그래프를 구성하는 과정에서 일 그룹에 해당하는 정점의 번호를 그냥 일의 번호로 설정하는 방식으로 수정하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

bool visited[1002] = { 0, };

int assignedWork[1002] = { 0, };
int getWorker[1002] = { 0, };

vector<int> graph[1002];

bool match(int worker);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, answer = 0;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		int numberOfWorks;
		cin >> numberOfWorks;

		while (numberOfWorks--) {
			int workNumber;
			cin >> workNumber;
			
			graph[i].emplace_back(workNumber);
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int i = 1; i <= N; i++) {
			visited[i] = false;
		}
		answer += match(i);
	}

	cout << answer;

	return 0;
}

bool match(int worker) {
	if (visited[worker] == false) {
		visited[worker] = true;
		for (auto possibleWork : graph[worker]) {
			if (getWorker[possibleWork] == 0 || match(getWorker[possibleWork])) {
				assignedWork[worker] = possibleWork;
				getWorker[possibleWork] = worker;
				return 1;
			}
		}
	}
	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

문제의 CLASS 를 보고 예상했겠지만, 세미나의 연습 문제로 나온 문제이다. 세미나에서 배우는 내용들이 어려운만큼, 연습 문제도 어렵고, 그렇다 보니 CLASS도 높은 문제들이 많은 것 같다.

더 쉬운 세미나를 지난 학기에 듣지 않은 것은 아니지만, 이렇게 본격적으로 PS를 시작하게 된 것은 최근이다. 그래서 세미나의 진도와 내 배경지식의 수준의 갭이 종종 많이 발생한다. 그걸 채우기 위해 CLASS 2 부터 계속 달려오고 있는 것이다. CLASS 4도 후딱 해치우고 5까지는 끝내둬야 진도를 따라잡을 수 있을 것 같다.

오늘의 PS는 여기까지!


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