BOJ 백준 1017 소수 쌍

 

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

 

[ 문제 요약 ]

• 배열이 주어지고, 서로 매칭을 하는데 매칭 조건은 두 숫자의 합이 소수일 때만 매칭 가능합니다.
• 이렇게 모든 쌍이 매칭이 된 후, 첫 번째 인자와 매칭 가능한 모든 후보들을 오름차순으로 출력합니다.

 

[ 테스트 케이스 설명 ]

6// 수의 크기 1<=50
1 4 7 10 11 12// 원소 수 1<=1,000, 중복되지 않음
답(없으면 -1출력) : 4 10

 

 

[ 알고리즘 분류 ]

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체
• 이분 매칭

 

[ 문제 해설 ]

 

먼저 두 숫자를 더했을 때 소수인 것을 빠르게 판별하기 위해 에라토스테네스의 체를 이용해 boolean 배열에 소수인 경우를 미리 담아 놓습니다.

 

그 후 더했을 때 소수인 모든 노드에 대해 인접 리스트를 생성해 놓습니다.

 

그리고 첫 번째 노드를 순회하며 첫 번째 노드의 연결 인자를 제외한 나머지가 모두 매칭이 가능했을 때 결과를 입력합니다.

 

일반 이분 매칭 문제와 크게 다르지 않습니다.

 

방문 유무를 체크하는 배열을 boolean으로 선언한다면 불필요한 연산이 생겨, 방문 체크를 O(1)에 해결할 수 있게 int형 배열로 선언하고 방문 시간을 입력함으로써 연산을 줄였습니다.

 

디테일은 코드를 통해 확인 가능합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Main{
	
	static int time;// 각 숫자의 방문 시간을 표시할 변수,
	static int N;
	static int arr[];// 초기값을 입력 받을 배열
	static int match[];// 이분 매칭시 매칭된 값을 담을 배열
	static int visitTime[];// 방문 시간을 표시함으로써 중복 방문 제거 
	static boolean isNotPrime[];// 소수면 false, 소수가 아니면 true
	static List<Integer> adList[];// 인접 노드 세팅, 더 했을 때 서로 소수인 것만
	static PriorityQueue<Integer> result;// 최종 결과는 오름차순 출력이므로 자동정렬되게 PriorityQueue사용
	
	public static void main(String[] args)throws Exception{
		setEratos();// 2000이하의 소수를 isNotPrime 배열에 마킹함 소수면 false값임
		inputAndInit();// 해당 함수에서 값을 입력받고, 인접리스트 생성	
		solve();// pairList에서 값을 꺼내 첫번 째인자와 꺼낸 인자를 제외하고 매칭시킴, 완벽하게 매칭되면 성공
	}
	static void setEratos() {
		isNotPrime = new boolean[2000];
		// 소수면 false;
		for(int i=2; i*i<2000; i++)
			if(!isNotPrime[i])
				for(int j=i*i; j<2000; j+=i)
					isNotPrime[j] = true;
	}
	static void inputAndInit() throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1];
		match = new int[N + 1];
		visitTime = new int[N + 1];
		result = new PriorityQueue<>();
		adList = new ArrayList[N + 1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
		{
			arr[i] = Integer.parseInt(st.nextToken());
			adList[i] = new ArrayList<>();
		}
		
		// 모든 인자들을 순회하며 인접리스트 생성
		for(int i=1; i<N; i++)
		{
			for(int j=i+1; j<=N; j++)
			{
				if(!isNotPrime[arr[i] + arr[j]])
				{
					adList[i].add(j);
					adList[j].add(i);
				}
			}
		}
	}
	static void solve() {
		// 첫번째 인자와 더해서 소수가 되는 모든 수를 순회 하면서 답을 구함
		for(int idx : adList[1])
		{
			Arrays.fill(match,0);
			int pair = 0;
			// 2번부터 끝까지 돌면서 매칭 가능한 개수를 찾음
			for(int i=2; i<=N; i++)
			{
				visitTime[1] = visitTime[idx] = ++time;
				if(dfs(i))
				{
					++pair;
				}
			}
			// 두개를 제외하고 모두 매칭이 되었으면 결과 저장
			if(pair == N - 2)
				result.add(arr[idx]);
		}
		
		StringBuilder sb = new StringBuilder();
		
		while(!result.isEmpty())
			sb.append(result.poll()).append(' ');
		
		System.out.print(sb.length() == 0 ? -1 : sb);
	}
	static boolean dfs(int idx) {
		for(int i : adList[idx])
		{
			if(visitTime[i] == time)
				continue;
			// 방문 시간 체크
			visitTime[i] = time;
			
			// 매칭 가능한지 재귀 탐색
			if(match[i] == 0 || dfs(match[i]))
			{
				match[i] = idx;
				return true;
			}
		}
		return false;
	}
}