목록Bipartite Graph (1)

코린이의 소소한 공부노트

Bipartite matching

1. Problem - 이분 매칭 알고리즘을 이용하여 X 집단이 Y 집단을 선택하는 방법을 찾아보자. - X 집단에 속하는 원소들이 Y 집단을 선택하는 조건이 주어질 때, 모든 조건을 만족하면서 X 집단의 모든 원소가 Y 집단의 원소를 선택하게 만든다. - 이때 X 집단에 속하는 원소 a, b에 대해 a!=b라면 Y(a)!=Y(b)가 성립해야 한다. 2. Input 1) List wishlist - wishlist[i] = X 집단의 원소 i가 선택하고자 하는 문자가 담긴 list 3. Output 1) X 집단의 원소 x와 x가 선택한 Y 집단의 원소 y를 차례대로 출력 4. Example // X = {1,2,3}, Y={A,B,C} // 1번의 조건: A, B, C // 2번의 조건: A // 3번..
Back-End/Algorithm 2023. 6. 20. 15:29
이전 Prev 1 Next 다음