3 - 1. Eratosthenes' Sieve 예제 (1963번: 소수 경로)

백준 1963번(소수 경로)

1963번: 소수 경로

 

안녕하세요.. 후 요즘 지원서 쓰고 코딩 테스트 본다고 정신이 없네요.ㅠㅠ

자주 글을 올려야 하는데... (자주.. 올려볼게요..)

엇! 근데, 잠깐 안한거같은데.. 많은게 바뀌었네요. ㅎㅎ (티스토리 짱짱맨!)

 

본론으로 넘어가서... 이 문제는 소수를 탐색하는 문제입니다.

일반적인 예제에서 에라토스테네스의 체만 쓰기엔 좀 아쉬워서 BFS에서 응용하는 문제를 가져와봤습니다.

 

 

 

문제 설명 자체가 한눈에 확 들어오진 않습니다..

그 와중에 정말 다행인 건 4자리의 소수만 확인해보면 되니까 생각보다 오래 걸리진 않을 것 같아요.

 

우선 각 테스트 케이스마다 우리가 구한 어떤 수가 소수인지 아닌지 계속 확인해줘야겠죠?

따라서 미리 에라토스테네스의 체를 이용해서 1000 ~ 9999 사이의 소수를 모두 찾아둡니다.

 

또한 탐색 시에 한 자리씩 바꿔야 하는데, 뭐 구현하기 편한 건 문자열이니까 그렇게 할까요...?

문자열은 쓸데없는 소모가 너무 많아서.. 되도록이면 피합시다.

(새로 생성한 문자열은 String pool에 등록도 하고, 문자 하나하나 쪼개어 바꾸는데 함수 호출도 계속해야 하고요.)

 

우리는 4자리 고정이니까 수식으로 처리합시다.

(실제로 문자로 처리했다가 메모리 초과 나는 경우가 꽤 많습니다. 가능하면 수식으로 처리해주세요.)

 

 

그리고 조건 몇 가지만 빼먹지 않도록 써놓고 바로 구현해볼게요.

1. 1000 미만의 수는 과정에 포함하지 않는다.
2. A -> B로 소수를 탐색 시 과정에 포함되는 값들도 항상 소수여야 한다.
3. 두 수가 같으면 바로 출력하고 넘어간다. (이건 문제에 없지만 당연하죠?)

우선 에라토스테네스의 체 구현부부터 볼게요.

설명은 따로 하지 않겠지만 잊어버리셨다면 다시 한번 읽어보시면서 천천히 이해해보세요.

 

에라토스테네스의 체 메소드

private static void prime() {
	isPrime = new boolean[INF];
	Arrays.fill(isPrime, true);
        
	isPrime[0] = isPrime[1] = false;

	for (int i = 2; i < INF; i++) {
		if(!isPrime[i]) continue;

		for (int j = i + i; j < INF; j += i) {
			isPrime[j] = false;
		}
	}
}

그리고 일반적인 너비우선탐색인데 다음 값 찾는 코드가 좀 많이 달라서 일단 보여드리고 설명드릴게요.

 

BFS 메소드

while (!q.isEmpty()) {
	int current = q.poll();
    
	int uni = current - (current % 10);							
	int ten = current - ((current % 100) - (current % 10));		
	int hun = current - ((current % 1000) - (current % 100));	
	int tho = current - (current / 1000 * 1000);	
			
	int[] nextSet = {tho, hun, ten, uni};	
	for(int i = 0; i < nextSet.length; i++){
		int next = 0;
				
		for (final int N: NUMS) {
			next = nextSet[i] + (N * (int) (Math.pow(10, 3 - i)));
	
			if (next > 1000 && next < INF && isPrime[next]) {
				if (isVisited[next] == 0) {					
					isVisited[next] = isVisited[current] + 1;
			
					if (next == prime2) {			
						return isVisited[next] - 1;
					}
			
					q.offer(next);
				}
			}
		}
	}
}

우선 큐에 담긴 초기 값 A를 가져와서 이를 각 자리를 하나씩 제거해줍니다.

예를 들어 숫자 8743이 들어오면 (8743이 소수라고 가정하고 봐주세요.)

8740(uni), 8703(ten), 8043(hun), 0743(tho) 이렇게요.

 

그리고 다음 숫자를 구하기 위해 해당 값들을 배열에 담고 밑의 반복문에서 다음 숫자를 생성합니다.

 

nextSet[i]는 우리가 하나씩 제거한 값들이고, NUMS 배열은 0 ~ 9까지 값들이 들어있습니다.

여기서 i가 나타내는 것은 해당 숫자의 공백 위치잖아요. 이를 이용해서 그 자릿수에 맞는 값을 만들어서 더해줍니다.

 

ex)

nextSet[i] = 8073, 변경전 / 이때 i = 1

아래의 수식을 통해 다음 값을 생성

next = nextSet[i] + (N * (int) (pow(10, 3 - i)));

 

N은 0 ~ 9까지 모두 들어가기 때문에 생성되는 숫자는 아래 10가지가 됩니다.

8073, 8173, 8273, 8373, 8473, 8573, 8673, 8773, 8873, 8973

 

뭐 이렇게 하고 이제 다음 값이 맞는지 확인을 해줘야 하죠.

이미 방문한 값인지? 소수가 존재하는지? 1000보다 작은 수가 존재하는지?

 

이 모든 조건에서 아직 탐색전의 소수이면서 1000 이상 9999 이하의 수라면 큐에 담기게 됩니다.

이렇게 하면 뭐 다른 건 별거 없습니다. 사실 뭐 그렇게 복잡한 코드도 아니라서 이미 다 이해하셨으리라 생각이 됩니다.

 

아 그리고 다음 소수를 찾으면 바로 탐색에 걸렸던 시간을 리턴을 했네요.

이 문제는 운 좋게 맞긴 했는데, 사실 저렇게 바로 반환은 좀 위험한 행동이니 최솟값을 저장할 변수를 만들어서 끝나구 반환하세요.

그리고 문제에 조건에 따라 최솟값이 변동이 없었다면 Impossible로 바꾸어 출력해주시면 됩니다.

 

 

1963.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	private static final String SPACE = " ";
	private static final String END_LINE = "\n";
	private static final String NO = "Impossible";

	private static final int INF = 10_000;
	private static final int[] NUMS = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

	private static boolean[] isPrime = null;
	private static int[] isVisited = null;

	private static int prime1 = 0;
	private static int prime2 = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());

        prime();	

		while (T-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), SPACE);
			prime1 = Integer.parseInt(st.nextToken());
			prime2 = Integer.parseInt(st.nextToken());

			isVisited = new int[INF];

			int result = 0;

			if (prime1 != prime2) {	
				result = bfs();
			}

			sb.append(result == -1 ? NO : result).append(END_LINE);	
		}
		System.out.println(sb.toString());
	}
	
	private static void prime() {
        isPrime = new boolean[INF];
		Arrays.fill(isPrime, true);
        
		isPrime[0] = isPrime[1] = false;

		for (int i = 2; i < INF; i++) {
            if(!isPrime[i]) continue;
			for (int j = i + i; j < INF; j += i) {
				isPrime[j] = false;
			}
		}
	}
	
	private static int bfs() {
		Queue q = new LinkedList<>();
		q.offer(prime1);

		isVisited[prime1] = 1;

		while (!q.isEmpty()) {
			int current = q.poll();
			int uni = current - (current % 10);							
			int ten = current - ((current % 100) - (current % 10));		
			int hun = current - ((current % 1000) - (current % 100));	
			int tho = current - (current / 1000 * 1000);	
			
			int[] nextSet = {tho, hun, ten, uni};	
			for(int i = 0; i < nextSet.length; i++){
				int next = 0;
				
				for (final int N: NUMS) {
                    next = nextSet[i] + (N * (int) (Math.pow(10, 3 - i)));
	
					if (next > 1000 && next < INF && isPrime[next]) {
						if (isVisited[next] == 0) {					
							isVisited[next] = isVisited[current] + 1;
			
							if (next == prime2) {			
								return isVisited[next] - 1;
							}
			
							q.offer(next);
						}
					}
				}
			}
		}
        
		return -1;
	}
}

흠.. 코드 줄이 좀 깨지는데 왜 이러는지 잘 모르겠네요... 휴

어쨌든 이렇게 이문제는 마무리가 됩니다.

 

출력 결과

 

이 문제는 최악의 경우 1000 ~ 9999 사이에서 소수를 찾지 못하고 끝나는 경우가 아마도 최악이겠네요.

자리마다 0 ~ 9까지 수를 바꾸니까 9 * 10 * 10 * 10인데, 그중에 소수 제외하고 다 걸러버리니까 빠르긴 빠릅니다.

(나중에라도 계산이 되면 다시 수정하도록 할게요.ㅠㅠ)

 

이해 안 가는 것이나, 질문 또는 잘못된 부분은 댓글로 지적 부탁드려요. 감사합니다.

 

 

 

문제의 저작권은 백준 온라인 저지에 있습니다.