질문: 전 A라는 여자를 좋아합니다. 우리는 매우 좋은 친구입니다. A의 가장 친한 친구 B는 저를 좋아합니…

질문: 전 A라는 여자를 좋아합니다. 우리는 매우 좋은 친구입니다. A의 가장 친한 친구 B는 저를 좋아합니다. 또 A는 제 절친인 C를 좋아하고, C는 다른 남자와 사귀고 있는 D라는 여자를 좋아합니다. 우리는 어떻게 해야 할까요? 답변: 그래프 이론의 Bipartite Matching 알고리즘을 적용할 수 있습니다. 다음과 같이 하세요: 모든 여자를 Part A의 정점들(a)로, 모든 남자를 Part B의 정점들(b)로 설정합니다. 정점 a에서 정점 b로, a가 b를 좋아하면 간선을 그립니다. 이 그래프는 bipartite 그래프가 됩니다 (Part A 내부와 Part B 내부에 간선이 없기 때문에, 단 친구들이 양쪽을 다 좋아하지 않는다고 가정합니다). 이 bipartite 그래프에서 maximum matching을 찾으세요. (GeeksforGeeks의 "Maximum Bipartite Matching" 링크를 참조하세요). maximum matching 결과로 매칭된 간선들을 얻게 될 것입니다. 매칭된 간선들은 서로 연결되어야 할 쌍을 나타냅니다. 만약 사람들이 서로를 얼마나 좋아하는지(또는 사랑하는지)를 알고 있다면, weighted bipartite matching 알고리즘을 사용할 수도 있습니다. 이 경우, 각 간선에 "좋아하는 정도"를 가중치로 할당한 후, 4번과 5번 단계를 반복하세요. 이 질문을 해 주셔서 감사합니다. 교수님께 배운 내용을 실제로 활용할 수 있는 문제를 드디어 찾았습니다. 2-3년 동안 공부했던 내용이에요. 추신: 프로젝트에서 작성한 weighted와 unweighted maximum bipartite matching 코드를 제공해드릴 수도 있습니다.