백준 18138 자바 - 리유나는 세일러복을 좋아해 (BOJ 18138 JAVA)

문제 : https://www.acmicpc.net/problem/18138

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/18100/BOJ_18138.java

 

 

  일단하나씩 매칭시키는 문제이니 이분 매칭 문제인건 알겠는데, 그래프에 간선이 없다. 그러니 로직은 간단히,

 

1. 입력을 받는다 (init())

2. 간선을 만든다 (makeEdge())

-> 이 때, w가 동일한게 안들어온다는 보장이 없으므로 w 대신 인덱스 번호로 새로 매칭시킨다. n개와 m개에 대해 0~n과 0~m을 노드로 하는 그래프로 바꾸면 된다. 간선을 만든 이후 w값은 필요없어진다. (62line)

3. 이분 매칭 돌린다 (matching())

 

  이분 매칭의 경우, m을 n이 가진다고 보고(owner 배열 -> 각 m 노드에 대해 배열값은 주인인 n을 뜻함), 각 n에 대해 하나씩 m을 매칭시킨다. 이 때 onwer[target]==-1 (현재 주인이 없음) 이거나, matching(owner[target]) (현재 주인이 있지만, 그 주인이 다른 m을 가질 수 있음) 이면 해당 m을 소유하고 true를 return하는 식이다.

 

예를들어 '2. 간선을 만든다'의 결과로 N과 M의 각 노드가 다음과 같다고 하자.

 

 

1. 우선 N-0과 M-0이 매칭된다. (onwer[0] = 0;)

 

2. 다음으로 N-1이 M-0을 확인했는데 이미 매칭이 되었으므로 (owner[0]==-1이 false), 다시 matching(owner[0])이 돌아가고, N-0이 M-1과 매칭되도록 변경되고 N-1이 M-0과 매칭된다. (owner[1] = 0; owner[0] = 1;)

 

3. 다음으로 N-2가 M-0을 확인하는데 M-0이 이미 매칭되었으므로 matching(1)이 돌아간다. matching(1)에서 M-1을 확인하는데 다시 점유되어 있으므로 matching(0)이 다시 돌고, 최종적으로 N-0이 M-2과 매칭되고, N-1이 M-1과 매칭, N-2가 M-0과 매칭되면서 3개 다 매칭되게 된다.

 

 

이런 식으로 이분 매칭을 진행할 시 최대한 매칭이 될 수 있다.