[BOJ 18138] 리유나는 세일러복을 좋아해/이분 매칭

www.acmicpc.net/problem/18138

18138번: 리유나는 세일러복을 좋아해

가끔 이 문제 관련해서 질문을 받습니다. '이거 정말 너가 만든 거야??'

 

네 맞아요...제가 만든 문제고 이분매칭 한창 배울 때 연습 겸해서 만들었던 문제입니다. 사실 딱봐도 이분매칭스러워 보이지 않나요?

 

(참고로 제 닉네임이 등장하는 문제들은 대부분 제가 만들었습니다. 14556 Balance 제외하고)

 

일단 이분매칭에 대해서 정말 간단하게 설명하자면, 이분 그래프가 있을 때(정점이 두 집합으로 나뉘어져서 각각의 집합 안에 있는 정점끼리는 간선이 존재하지 않음)거기서 최대 매칭을 구하면 됩니다. 매칭은 간략하게 말하자면 간선들의 집합인데, 각각의 간선들과 연결된 정점들이 중복되어서는 안됩니다. 와닿을만한 예시를 하나 들자면, 이성애자 남성 n명과 이성애자 여성 m명이 있고, 그들은 모두 이성애자여서 각각 이성에게만 관심이 있다고 할 때, 서로 관심이 가는 두 사람을 간선으로 연결한다면 여기서 나올 수 있는 최대의 커플 수를 구하여라...같은 문제와 비슷할 수 있겠네요.

 

사실 최대 유량 문제에서 모든 간선의 크기가 1인 특수한 경우라고도 볼 수 있겠네요.

 

아무튼간에, 그래서 이 문제는 그냥 전처리가 아주 조금만 필요한 이분 매칭 문제입니다. 세일러 카라들의 집합과 세일러복들의 집합을 잇는 간선들을 구해서 그 이분 그래프에서 최대 매칭 크기를 구하면 되고, 이는 알려진 여러 알고리즘들을 사용하면 됩니다. 대표적으로는 호프크로프트-카프 알고리즘이 있겠네요.

 

그래서 전처리를 잘해준 뒤에(붙일 수 있는 세일러카라와 세일러복을 잘 구별해서)간선으로 이어주고, 그렇게 해결하면 되는 문제입니다.