자체 해결하였습니다..
별거 아닌 실수 였는데요 ㅜㅜ
bimatching 함수에서는 0번째와 i번째를 묶었다고 가정하고 그 나머지에 대해 매칭하여 매칭 개수를 가져옵니다.
dfs함수는 현재 홀수배열의 cur번째 index에서 짝수배열로 이동할 수 있는지 여부를 판단해줍니다.
가장 큰 실수가 back이라는 배열에서 나왔는데요.
back배열은 짝수 배열의 인덱스가 홀수 배열에 연결이 되어있지 않다면 -1, 연결이 되어있다면 연결된 홀수 배열의 인덱스를 저장합니다.
그런데 저는 이 back 배열을 처음에
for(int i=0; i<N; i++)
back[i]=0;
으로 해서 본의 아니게 연결이 되어있지 않아야할 배열이 0번째 인덱스를 가리키게 되었습니다.
back[i]=0; 이걸-1로 바꾸니까 해결됬네요. ㅜㅜ
barcelonamessi 7년 전
이분매칭 시도해서 풀어봤는데 왜 틀렸는지 잘 모르겠습니다.
코드가 좀 복잡해서 봐주실지 모르겠지만 ㅜㅜ 나름 제 코드 내용 적어볼게요
자료구조 : 홀수만 저장하는 배열 , 짝수만 저장하는 배열
전체 배열에 입력 받으면서 짝수면 짝수배열에 저장, 홀수면 홀수배열에 저장, 각각 홀수와 짝수의 개수를 저장하면서 올려줌.
입력받고 sosu 배열에 1이면 소수 0이면 소수 아니게 저장함.
입력 다 받고나서 홀수의 개수와 짝수의 개수가 다르면 -1 출력
홀수의 개수와 짝수의 개수가 같다면
(개수가 n개라면 0~n-1 인덱스 까지 배열이 저장되있음.)
1~n-1 인덱스 검사하면서 첫번째 입력받은 숫자와의 합이 소수이면
이분 매칭을 시도함.
이분매칭할 때 홀수 배열, 짝수 배열을 이용하고 만약 과정중에 절대로 바뀌면 안되는 두 개의 수가 발견되면
진행을 건너뛰게하였음. 이 과정에서 이분매칭의 숫자가 n/2-1개이면(1개는 이미 처음에 했으므로 뺌)
소수쌍 성공으로 받아들이고 벡터에 저장함.
이과정 끝내고 벡터가 비었다면 만족하는것이 없으므로 -1 출력 . 그 외엔 벡터를 정렬하고 오름차순으로 출력.
제 예상은 dfs과정에서 완벽히 정해진 수를 건너뛰는과정 (arr[0]이나 arr[0]과 합해서 소수가 된 수는 다른 수와 매칭되어서는 안되므로
건너뜀) 에서 착오가 있는것 같은데 정확히모르겠습니다