[백준] No.1017 - 소수 쌍 (C++, 이분 매칭)

문제

 

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

1017번: 소수 쌍

 

풀이

 

solved.ac 난이도: Platium 3

 

짝수와 홀수로 두 집합을 만들어 이분 매칭으로 해결하는 문제.

이분 매칭을 잘 모른다면 다음 기본 문제를 먼저 해결해보고 오자.

[백준] No.2188 - 축사 배정 (C++, 이분 매칭)

 

 

두 자연수를 더하는 경우는 3가지로 분류할 수 있다.

 

1. 짝수 + 짝수

짝수끼리 더한 수는 짝수이기 때문에 소수가 될 수 없다.

 

2. 홀수 + 홀수

홀수끼리 더한 수도 짝수가 되기 때문에 소수가 될 수 없다.

 

3. 짝수 + 홀수

2를 제외한 모두 소수는 홀수 이기 때문에 짝수와 홀수를 더하는 경우에만 소수가 나올 가능성이 있다.

 

 

따라서 입력받는 자연수를 두 가지 집합인 짝수와 홀수 집합으로 분리하자.

첫 번째 수(first_num)가 짝수라면 A 집합에는 첫 번째 수와 모든 짝수를, B집합에는 홀수를 저장하자.

만약 첫번째 수가 홀수 라면 반대로 A집합에는 첫 번째 수와 모든 홀수를, B집합에는 짝수를 저장하자.

 

입력을 두 가지 집합으로 이분하였으므로 정점들에 간선을 연결해주자.

A집합의 수(a)와 B집합의 수(b)를 더한 값이 소수인 경우에만 a에서 b로의 간선을 연결해주면 된다.

이때 소수의 판정은 빠르게 소수를 판별할 수 있는 에라토스테네스의 체 알고리즘을 이용하였다.

 

 

 

 

문제의 예제 입력을 그래프로 표현하면 다음과 같다.

 

6

1 4 7 10 11 12

 

 

이제 첫 번째 수를 먼저 B 집합의 수와 짝을 지은 다음, 나머지 수들을 이분 매칭하여 모든 수가 매칭 되는 지 확인하면 된다.

이때 첫번째 수는 이미 매칭이 되었으므로 DFS로 재귀 호출되어 다른 수와 매칭 되는 것을 막아주자.

 

 

이분 매칭 DFS

bool DFS(int a_idx){
  //a가 첫번째 수라면 이미 다른 수와 연결되어 있음
  if(a_idx == 0 || visited[a_idx])
    return false;
  visited[a_idx] = true;
 
  for(int i=0; i<adj[a_idx].size() ; ++i){
    int b_idx = adj[a_idx][i];
 
    if(b_match[b_idx] == -1 || DFS(b_match[b_idx])){
      a_match[a_idx] = b_idx;
      b_match[b_idx] = a_idx;
      return true;
    }
  }
  
  return false;
}

 

 

이번 문제는 디버깅에 애를 먹었는데, 두 자연수의 합의 최댓값은 1999인데 소수 판정 값을 1000까지만 해서 틀린 것이었다...

항상 느끼지만 디버깅을 하고 틀린 코드를 찾았을 때, 대부분이 어이없는 실수인 것 같다...

 

코드