1017번: 소수 쌍

1017번: 소수 쌍 - 이분 매칭

짝수 개의 수 리스트가 주어질 때, 2개씩 짝지었을 때의 합이 모두 소수가 되는 경우의

첫 번째 수와 연결 되어 있는 수를 오름차순으로 출력하는 문제이다.

입력에 주어지는 수들은 중복되지 않으므로 1이 두 번 주어질 수는 없다.

소수는 2보다 클 경우 모두 홀수이므로 합이 홀수가 될 때의 경우를 생각해보자.

홀수는 짝수와 홀수가 더해질 때만이 홀수가 되므로 2개의 그룹으로 나눠지고

이들을 짝지어 이어주는, 즉 이분매칭 문제가 되게 된다.

짝수 그룹, 홀수 그룹으로 나누고 이들을 잇는 간선들은 합이 소수가 될 경우 이어준다.

이 그래프의 최대 매칭이 N/2일 경우에 답으로 가능할 경우인 것을 알 수 있다.

약간의 함정이 숨어있는 문제다. 출력해야할 부분은 첫 번째 수와 연결되어 있는 수로,

첫 번째수가 홀수일 지, 짝수일 지 알 수 없으며 이 또한 잘 구별해서 판단해줘야 한다.

첫 번째 수와 연결된 수가 궁금한 것이므로 처음에 그래프에서 간선을

첫번 째 수를 제외하고 연결 한 뒤

모든 반대 그룹의 정점들과 조건이 만족할 경우(합이 소수일 경우) 간선을 이어주고

최대 매칭을 구하고 다시 간선을 삭제해 주는 과정을 반복하여 답을 계산하면 풀 수 있는 문제이다.