백준 11376 자바 - 열혈강호 2 (BOJ 11376 JAVA)

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

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11300/BOJ_11376.java

 

  기본적인 형태의 이분 매칭 문제이다. 다만 한 사람당 2개의 일을 할 수 있으므로, n을 2배로 늘렸다. 이 때 간선 정보는 n개만 유지할 수 있도록 하는것이 좋다. 내 경우엔 그래서 간선정보를 n개 받아두고, e[n/2] (12line) 형태로 받아온다. 사실 이분 매칭에서 매칭시킬 때, 기본형태에서 그 안에 들어있는 n의 번호 자체는 중요한게 아니므로(같던 다르던 상관 없음) 코드의 45line처럼 for문 돌릴 필요 없이, 그냥 그 내에서 다시한번 2번을 돌리도록 해도 된다. (45line의 for문 내에 'for(int j = 0; j < 2; j++) ~'). TMI로, for each문이 깔끔하긴 하지만, 12line처럼 받은 후에 직접 'edge.get(i)'으로 얻어오는게 더 빠르다.