글 읽기 - 1017 소수쌍 문제 질문드립니다ㅠㅠ

mozzi01331 4년 전 0

안녕하세요, 인터넷에서 찾을 수 있는 풀이들과 대조해 봤는데도 왜 틀렸는지를 찾기 어려워서 여기에 질문글을 올립니다ㅠ.ㅠ

푸는 로직은 아래와 같습니다.

n개만큼 숫자 입력을 받고, 첫번째 입력과 같은 성질(짝/홀수)는 A, 다른 성질은 B로 모읍니다.
A와 B의 합 중 소수인 경우는 간선을 이어줍니다( canAdd[aIdx] = bIdx)
이후 첫번째 수(당연히 A[0]이 될)에 이어진 간선의 수만큼 이분탐색을 수행합니다.
1. aMatch[0]은 해당 간선의 idx(i)로 초기화합니다
2. bMatch[i]도 0으로 초기화합니다.
3. 0번을 제외한 나머지 A간선의 개수만큼 dfs를 돌리고, return값을 result 변수에 업데이트합니다.
4. result값이 n/2일 경우, pq에 넣습니다.

제가 놓친 부분 혹은 구현하지 못한 부분이 있는 것 같은데 뭔지 모르겠습니다ㅠㅠ... 감사합니다!

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int N;
int arr[52], aMatch[26], bMatch[26];
bool visited[26]; // visited[idx] : A[idx]가 이미 visited인가?
vector<int> canAdd[26]; // canAdd[i] : A[i]와 연결되는 B의 idx
vector<int> A, B;

priority_queue<int> pq;

int dfs(int a) {
	if (visited[a]) {
		return 0;
	}

	visited[a] = true;

	for (int b : canAdd[a]) {
		if (bMatch[b] == -1 || dfs(bMatch[b])) {
			aMatch[a] = b;
			bMatch[b] = a;
			return 1;
		}
	}

	return 0;
	
}

void biPartiteMatch() {

	for (int i : canAdd[0]) {
		int result = 1;
		memset(aMatch, -1, sizeof(aMatch));
		memset(bMatch, -1, sizeof(bMatch));
		memset(visited, 0, sizeof(visited));

		aMatch[0] = i;
		bMatch[i] = 0;
		visited[0] = true;

		for (int j = 1; j < A.size(); j++) {
			result += dfs(j);
		}

		if (result == N / 2) {
			pq.push(-B[i]);
		}
	}

	if (pq.empty()) {
		cout << -1 << endl;
	}
	else {
		while (!pq.empty()) {
			cout << -(pq.top()) << " ";
			pq.pop();
		}
		cout << endl;
	}

	return;
}

bool isPrime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	cin >> N;

	cin >> arr[1];
	A.push_back(arr[1]);

	for (int i = 2; i <= N; i++) {
		cin >> arr[i];
		(arr[i] % 2 == arr[1] % 2 ? A : B).push_back(arr[i]);
	}

	if (A.size() != B.size()) {
		cout << "-1" << endl;
		return 0;
	}

	for (int i = 0; i < A.size(); i++) {
		for (int j = 0; j < B.size(); j++) {
			if (isPrime(A[i] + B[j])) {
				canAdd[i].push_back(j);
			}
		}
	}

	//탐색 및 출력
	biPartiteMatch();
    
    return 0;
}

mozzi01331 4년 전 0

셀프로 해결했습니다ㅠ.ㅠ 임의의 반례

1 2 3 4 5 6 7 8 을 했더니 답인 2 4 6이 나오지 않더라구요..

틀린 원인은... dfs에서의 초기에 탐색을 멈추는 조건이었습니다.

0번째 인덱스에 대해서는 이미 할당을 해주고 넘어가기 때문에 해당 조건에 대해서는 더이상 탐색하지 않으려고 visited[a]가 true면 return 0을 해줬었는데, 당연히 그러면 a가 0이 아닌 1,2,3인 경우에도 추가적인 탐색을 해주지 않기 때문에 에러가 납니다.

a==0인 경우 return 0으로 변경하고, 그 외의 경우에는 visited[a] ==visitCnt 인 경우에만 return 1을 수행했습니다.

visitCnt로 체크하는 이유는 같은 탐색을 무한루프로 도는 것을 방지하기 위함입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1017 소수쌍 문제 질문드립니다ㅠㅠ

mozzi01331 4년 전 0

mozzi01331 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말