이분매칭_작업 할당하기[1/1]

[ 이분 매칭이란? ]

• 1:1 매칭 개념으로 하나의 노드에 하나만 효율적으로 할당하는 방법
• 기본 1:1 매칭이지만 조금 고치면 특정 노드는 2:1매칭 등으로 수정 가능
• 응용하기 나름​

예를 들어 실생활에서 여러 개의 희망 사항을 모아서 가장 효율적으로 배분하는 방법이라고 볼 수 있습니다. 청소 구역 신청을 예로 들어보겠습니다. 아래와 같이 학생들이 각자 희망하는 청소구역을 여러개 적어서 냈을 때, 가장 효율적으로 배분하는 방법입니다. 몇 명 안되면 손으로 하면 되는데 학생수가 많으면 손으로 하기보단 코딩해서 뽑아내는게 더 빠르겠네요.

 

 

 

---

 

간단히 방법론에 대해 설명하자면 아래와 같은 과정을 통해 진행됩니다.

 

 

 

 

 

 

---

 

위 로직을 그대로 코드로 옮기면 됩니다. 다들 C++로 짜는지라 저 편한대로 C로 구현해봅니다. 입력 받을 때 한 사람이 몇 개까지 써낼지 모르기 때문에 입력 함수를 따로 만들었습니다.

 

※ 입력 예시
첫번째 숫자가 학생, 뒤의 숫자들이 지망하는 구역입니다.
0 0 2
1 0 2
2 1 3
3 0 3
4 1 2

희망 구역은 원하는만큼 작성 가능합니다.
0 0 1 2 3 4
1 0 2
2 1 3
3 3
4 1 2 3

 

---

 

 

 

 

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define NUM 5  // 학생 수, 한명 당 1개씩은 무조건 받음

typedef struct c clean;
struct c {
	int spot;  // 희망 청소 장소
	clean* next;  // 다음 지망 장소
};

int bipartite_matching(clean** student, int* student_x, int* clean_spot, int i);
void read_line(FILE* fp, clean** student);
void create_clean(clean** student, int i, int spot);
void print_cleaning(int* clean_spot, int* student_x);

int main()
{
	clean* student[NUM] = { NULL };  // 학생 배열
	int student_x[NUM] = { 0 };  // 청소 구역 배당 여부 (1이면 배당 완료)
	int clean_spot[NUM];  // 구역별 청소 담당자 배열

	/* clean_spot 초기화 */
	for (int i = 0; i < NUM; i++)
		clean_spot[i] = -1;

	read_line(stdin, student);  // 정보 입력	
	
	for (int i = 0; i < NUM; i++)  //이분매칭 수행
		bipartite_matching(student, student_x, clean_spot, i);

	/* 결과 출력 */
	print_cleaning(clean_spot, student_x);

	return 0;
}

/* 이분매칭 수행 */
/* parameter : student, student_x, clean_spot 배열, 학생 번호 i */
/* return : 성공 매칭됐으면 0, 매칭할 곳이 없으면 -1 */
int bipartite_matching(clean** student, int* student_x, int* clean_spot, int i)
{	
	/* 연결된 희망 청소 구역을 탐색 */
	while (student[i] != NULL)
	{
		int a = student[i]->spot;  // 현재 희망 구역 정보 저장
		clean* p = student[i];
		student[i] = student[i]->next;  // 해당 노드 삭제 (첫 번째 연결리스트) 
		free(p);

		if (clean_spot[a] != -1 && // 해당 구역이 비어 있지 않고 소유자도 갈 곳이 없다면
			bipartite_matching(student, student_x, clean_spot, clean_spot[a]) == -1)
			continue;
				
		clean_spot[a] = i;  // 해당 구역이 비어있다면 값을 넣어줌
		student_x[i] = 1;
		return 0;  // 수행됐으면 0 리턴		
	}

	return -1;	// 아무곳에도 매칭되지 못했으면 -1 리턴
}


/* 학생 수 만큼 원하는 청소 구역 정보를 받음 */
/* parameter : stdin 또는 파일, student 배열 */
/* return : void */
void read_line(FILE* fp, clean** student)
{
	/* 입력 받아 처리, 학생 수만큼 입력 줄이 생김 */
	for (int i = 0; i < NUM; i++)
	{
		int j = 0, count = 0;
		int temp[NUM + 1] = { 0 };
		char c;
		while ((c = getc(fp)) != '\n' && c != EOF)
		{
			// 공백을 만날 때까지 숫자로 저장 (숫자만 인식)
			if (!isspace(c) && c < 58 && c > 47)
				temp[j] = (temp[j] * 10) + (c - '0');
			else if (isspace(c))  // 공백 만나면 다음 숫자로 인식
			{
				j++;
				count++;  // 저장된 숫자 갯수 
			}
			else  // 숫자 외 입력시 에러 처리
			{
				puts("숫자만 입력해 주세요.");
				exit(1);
			}
		}
		count++;

		/* 입력된 정보로 생성 (temp[0]은 학생정보, 나머지는 희망 구역 */
		for (int i = 1; i < count; i++)
			create_clean(student, temp[0], temp[i]);
	}
}


/* 청소 희망구역 생성 */
/* parameter : student 배열, 학생 번호, 희망 청소구역 */
/* return : void (메모리 할당 실패 시 프로그램 종료) */
void create_clean(clean** student, int i, int spot)
{
	clean* temp;
	if ((temp = (clean*)malloc(sizeof(clean))) == NULL)
		exit(2);
	temp->spot = spot;
	temp->next = NULL;

	if (student[i] == NULL)  // 아직 저장된 청소 구역 하나도 없을 때 
		student[i] = temp;
	else  // 저장된 청소 구역이 하나라도 있을 때
	{
		clean* p = student[i];
		while (p->next != NULL)
			p = p->next;
		p->next = temp;  // 마지막에 붙여줌
	}
}


/* 청소구역 담당 출력 */
/* parameter : clean_spot, student_x 배열 */
/* return : void */
void print_cleaning(int* clean_spot, int* student_x)
{
	char* student[NUM] = { "홍길동", "임꺽정", "심청이", "전우치", "손오공" };
	char* spot[NUM] = { "칠판", "복도", "바닥", "창문", "화장실" };
	printf("\n");
	/* 배정된 학생 출력 */
	for (int i = 0; i < NUM; i++)
	{
		if (clean_spot[i] != -1)
			printf("  %d %s : %s(%d)\n", i, spot[i], 
                      student[clean_spot[i]], clean_spot[i]);
	}
	/* 배정안된 학생, 장소 출력 */
	printf("  배정안된 장소 : ");
	for (int i = 0; i < NUM; i++)
	{
		if (clean_spot[i] == -1)
			printf("%s(%d) ", spot[i], i);
	}
	printf("\n  배정안된 학생 : ");
	for (int i = 0; i < NUM; i++)
	{
		if (student_x[i] == 0)
			printf("%s(%d) ", student[i], i);
	}
	printf("\n");
}

 

---

 

연결리스트 자료구조를 버리고 2차원 배열을 사용한 버전입니다. 메모리 효율성을 버리는 대신 코드가 매우 간결해집니다. (2차원 배열 크기를 NUM*NUM으로 잡아줘야 하니 비는 공간들이 많이 생깁니다. 수가 늘어날 수록 메모리 비효율이 커집니다.)

 

 

 

 

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define NUM 5
void read_line(FILE* fp, int student[][NUM]);
int bipartite_matching
(int student[][NUM], int student_x[NUM], int clean_spot[NUM], int i);
void print_cleaning(int* clean_spot, int* student_x);

int main()
{
	int student[NUM][NUM];  // 학생 배열
	int student_x[NUM] = { 0 };  // 할당 완료된 학생 여부
	int clean_spot[NUM];  // 구역별 청소 담당자 배열

	/* student 초기화 */
	for (int i = 0; i < NUM; i++)
		for (int j = 0; j < NUM; j++)
			student[i][j] = -1;

	/* clean_spot 초기화 */
	for (int i = 0; i < NUM; i++)
		clean_spot[i] = -1;

	read_line(stdin, student);  // 정보 입력	
	for (int i = 0; i < NUM; i++)  // 이분매칭 수행
		bipartite_matching(student, student_x, clean_spot, i);
	
	print_cleaning(clean_spot, student_x);

	return 0;
}

/* 이분 매칭 수행 */
/* parameter : student, student_x, clean_spot 배열 */
/* return : 지정구역에 할당되면 0, 실패하면 -1 */ 
int bipartite_matching
(int student[][NUM], int student_x[NUM], int clean_spot[NUM], int i)
{
	for (int j = 0; j < NUM; j++)
	{
		if (student[i][j] == -1) continue;  // 이미 방문한 노드는 패스

		// 방문하는 노드에 소유자가 있는데 그 소유자가 다른 곳으로 이동하지 못할 경우 패스
		else if (clean_spot[student[i][j]] != -1 &&
			bipartite_matching(student, student_x, 
                                      clean_spot, clean_spot[student[i][j]]) == -1)
		{
			student[i][j] = -1;  // 방문해서 확인 완료했으면 -1 처리
			continue;
		}

		clean_spot[student[i][j]] = i;
		student_x[i] = 1;
		student[i][j] = -1;  // 방문해서 확인 완료했으면 -1 처리
		return 0;
	}

	return -1;  // 다 찾아봤는데 갈 곳 없으면 -1 리턴
}


/* 학생 수 만큼 원하는 청소 구역 정보를 입력받음 */
/* parameter : stdin 또는 파일, student 배열 */
/* return : void */
void read_line(FILE* fp, int student[][NUM])
{
	/* 입력 받아 처리, 학생 수만큼 입력 줄이 생김 */
	for (int i = 0; i < NUM; i++)
	{
		int j = 0, count = 0;
		int temp[NUM + 1] = { 0 };
		char c;
		while ((c = getc(fp)) != '\n' && c != EOF)
		{
			// 공백을 만날 때까지 숫자로 저장 (숫자만 인식)
			if (!isspace(c) && c < 58 && c > 47)
				temp[j] = (temp[j] * 10) + (c - '0');
			else if (isspace(c))  // 공백 만나면 다음 숫자로 인식
			{
				j++;
				count++;  // 저장된 숫자 갯수 
			}
			else  // 숫자 외 입력시 에러 처리
			{
				puts("숫자만 입력해 주세요.");
				exit(1);
			}
		}
		count++;

		/* 입력된 정보로 생성 (temp[0]은 학생정보, 나머지는 희망 구역) */
		for (int i = 1, j = 0, w = 0; i < count; i++, j++)
			student[temp[0]][j] = temp[i];
	}
}


/* 청소구역 담당 출력 */
/* parameter : clean_spot, student_x 배열 */
/* return : void */
void print_cleaning(int* clean_spot, int* student_x)
{
	char* student[NUM] = { "홍길동", "임꺽정", "심청이", "전우치", "손오공" };
	char* spot[NUM] = { "칠판", "복도", "바닥", "창문", "화장실" };
	printf("\n");
	/* 배정된 학생 출력 */
	for (int i = 0; i < NUM; i++)
	{
		if (clean_spot[i] != -1)
			printf("  %d %s : %s(%d)\n", i, spot[i], 
                   student[clean_spot[i]], clean_spot[i]);
	}
	/* 배정안된 학생, 장소 출력 */
	printf("  배정안된 장소 : ");
	for (int i = 0; i < NUM; i++)
	{
		if (clean_spot[i] == -1)
			printf("%s(%d) ", spot[i], i);
	}
	printf("\n  배정안된 학생 : ");
	for (int i = 0; i < NUM; i++)
	{
		if (student_x[i] == 0)
			printf("%s(%d) ", student[i], i);
	}
	printf("\n");
}