[AC] 1017 소수 쌍

출처 : https://www.acmicpc.net/problem/1017

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1017.cpp

이 문제는 나를 참 힘들게하였고 덕분에 이분매칭에 대해 공부하게된 계기를 준 문제이다. 문제자체는 별거아닌것 같지만 참 별거인문제이다.

5달전 처음으로 도전하여 실패하였고 최근 3주간 매주 도전하여 결국 풀어냈다.

처음 이문제을 단순 DFS로 도전하여 실패하고 한 유저분이 이분매칭을 사용하라고해서 공부를 했다.

그리고 이문제에 대한 다양한 접근법을 생각해봤다.

결국 소수가 되기위해서는 홀수+짝수인 경우만 가능하기에 (홀수+홀수, 짝수+짝수는 결국 짝수가 되고 이는 절대 소수가 아니다.) 두개의 입력을 분리하여 보관하고 하나씩 매칭하는 방법을 하려했다. 그런데 아무리 생각해도 이렇게 하니 일이 복잡해지는 느낌이었다.

더 간단히 더 기본에 충실한 알고리즘을 생각하다가 저번에 푼 이분그래프 문제가 생각이 났다. 그 문제역시 입력을 복제하여 두개의 그룹처럼 생각하고 접근하였는데 그 방법을 여기서 도입해도 될거라 생각했다.

그래서 이런 로직을 세웠다.

1. 먼저 소수확인용 배열을 만들고 함수로 배열을 완성한다.

2. int형의 일반 배열에 인풋을 담아둔다.

3. 2번에서 받은 배열로 각 위치의 숫자당 소수가 이루어질수있는 녀석을 푸시하여 2차원 벡터를 만든다. 여기서 그래프로 만들기위해 반대선을 만들지 않는 이유는 결국 나는 하나의 입력을 가지고 전부 돌기 때문에 굳이 하지 않아도 반대선이 체크가 되기 때문이다.

3. 과거 수차례 작성했던  bpm함수를 만든다. 하지만 여기서 중요한것은 첫번째수와 매칭되는 수는 제외하고 생각해야 한다는 점이다. 그래서 38, 39번라인으로 bmatch를 값을 주고, 45번줄에 이미 사용함을 체크한다. 그리고 dfs함수는 과거 작성했던 이분매칭소스와 완벽히 동일하다.

4. 이 함수에서 매칭값이 n-2가 나오면 모든 수에 대해 매칭이 완전히 이루어진다는 말이므로 이 값을 ans에 푸시한다. 보통은 매칭값이 한쌍이냐 아니냐로 따지지만 이문제에서 나는 하나의 인풋을 두개의 그룹으로 나누어 생각하였기 때문에 각 수마다 전부 매칭이 루어지는지 체크해야만 한다.

5. ans가 비어있으면 -1 아니라면 sort를 해준다.

이렇게하니 소스도 그렇게 길지 않았고, 로직도 간단히 하여 풀렸다. 특별한 기술도 들어가지 않고, 그냥 기본에 충실한 이분매칭법으로 풀수있었다. 풀다보니 과거 DFS처음 공부할때 풀었던 Prime Ring Problem문제가 생각났다. 아마 나는 이문제를 잊지 않을것 같다.