[백준] G5 1963 소수 경로 (java)

www.acmicpc.net/problem/1963

1963번: 소수 경로

 

풀이

 

1) 에라토스테네스의 체를 이용하여 1~9999 까지의 소수를 판별한 prime[] 을 만든다.

2) 입력받은 숫자A를 파라미터로 넣고 bfs를 돌린다. Queue의 제너릭 Node에는 숫자와 횟수를 담는다.

2-1) 숫자A를 StringBuilder에 담는다. (한 자리씩 치환하는것을 쉽게하기 위함)

2-2) 4자리이므로 4개만큼 for문을 돌리는데 숫자는 0~9까지이므로 10개만큼 for문을 또 돈다.

2-3) 각 자리마다 10번씩 돌면서 소수인지 판별하여 소수이면 방문체크를 한 뒤 queue에 넣는다. (front.cnt +1)

2-4) queue.poll()이 B가 되면 output에 append

3) output.close();

 

주의사항

 

1) 없다

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G5_1963_소수경로 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer tokens;
	static int T, A, B;
	static boolean prime[], isVisited[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		prime = new boolean[10000];
		isVisited = new boolean[10000];
		Arrays.fill(prime, true);
		makePrime();
		T = Integer.parseInt(input.readLine());
		for(int t=0; t<T; t++) {
			tokens = new StringTokenizer(input.readLine());
			A = Integer.parseInt(tokens.nextToken());
			B = Integer.parseInt(tokens.nextToken());
			
			bfs(A);
			Arrays.fill(isVisited, false);
		}
		output.close();
	}

	private static void bfs(int num1) throws IOException {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(num1, 0));
		isVisited[num1] = true;
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			
			if(front.num == B) {
				output.append(front.cnt + "\n");
				return;
			}
			
			for(int i=0; i<4; i++) {
				StringBuilder temp = new StringBuilder();
				temp.append(front.num);
				for(int j=0; j<10; j++) {
					temp.setCharAt(i, (char) (j + '0'));
					int tmp = Integer.parseInt(temp.toString());
					if(prime[tmp] && !isVisited[tmp] && tmp>=1000 && tmp<10000) {
						queue.offer(new Node(tmp, front.cnt+1));
						isVisited[tmp] = true;
					}
				}
			}
		}
		output.append("Impossible\n");
		return;
	}
	
	static class Node{
		int num;
		int cnt;
		public Node(int num, int cnt) {
			super();
			this.num = num;
			this.cnt = cnt;
		}
	}

	private static void makePrime() {
		for(int i=2; i*i<10000; i++) {
			for(int j=i+i; j<10000; j+=i) {
				prime[j] = false;
			}	
		}
	}

	static String src =
			"3\r\n" + 
			"1033 8179\r\n" + 
			"1373 8017\r\n" + 
			"1033 1033";
}

 

 

후기

 

 뭔가 내 생각이 맞나 싶어서 솔루션을 보고 시작했다. 거의 비슷했지만 다른점은 나는 한자리씩 치환하면서 그 숫자를 검사 함수에 넣어서 prime number인지 판별하여 bfs를 돌려고 했지만 미리 prime number를 10000까지 구한 다음 시작한다는 점. 또 에라토스테네스의 채를 이용하여 소수를 구한다는 점이 달랐다.

다른건 몰라도 소수를 빠르게 찾을 수 있는 에라토스테네스의 채라는 기술을 익힌 것만으로 이 문제를 푼 의미가 있었다.