[백준] 소수경로 (java) Bfs

2020-04-10

소수 경로 (백준> Dfs_Bfs)

문제 링크

문제설명

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

  • “이제 슬슬 비번 바꿀 때도 됐잖아”
  • “응 지금은 1033으로 해놨는데… 다음 소수를 무엇으로 할지 고민중이야”
  • “그럼 8179로 해”
  • “흠… 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데… 예를 들면… 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
  • “흠…역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
  • “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

예제 입력 1 복사

3
1033 8179
1373 8017
1033 1033

예제 출력 1 복사

6
7
0


풀이

package Dfs_Bfs;

import java.util.*;
import java.io.*;

public class beak_소수경로 {

	public static boolean[] prime;
	
	//num부터 숫자 바꿔보기
	//type은 자리수, t는 0~9까지
	public static int changeNum(int num, int type, int t) {
		int result = 0;
		
		switch(type) {
		case 1: //1000의 자리
			result = t*1000;
			result += num - num/1000 * 1000;
			break;
		case 2: //100의 자리
			result = t*100;
			result += (num/1000 * 1000) + (num - num/100 *100);
			break;
		case 3: //10의 자리
			result = t*10;
			result += (num/100*100) + (num- num/10 *10);
			break;
		case 4: //1의 자리
			result = t;
			result += num/10*10;
			break;
		}
		return result;
	}
	
	public static boolean isPrime(int n) {
		if(n == 1)	return false;
		
		for(int i=2; i<n; i++) {
			if(n%i == 0)
				return false;
		}
		return true;
	}
	
	public static void bfs(int start, int end) {
		int count = -1;
		
		boolean visited[] = new boolean[10000];
		
		//int 배열로 초기화한 queue
		Queue<int[]> qu = new LinkedList<int[]>();
		qu.add(new int[] {start,0}); //처음에 큐에 {start,0} 넣음
		
		while(!qu.isEmpty()) {
			//빼기전에 num, cnt에 넣기
			int num = qu.peek()[0];
			int cnt = qu.peek()[1];
			
			qu.poll();//빼고
			if(num == end) {
				if(count == -1 || count > cnt)
					count = cnt;
				continue;
			}
			
			if(num<1000 || visited[num])
				continue;
			
			//이미 방문했던곳이 아니라면
			visited[num] = true;
			
			//순차적으로 1000이 넘으면서 소수인지 확인
			//i는 자리수, j는 0~9까지
			for(int i=1; i<=4; i++) {
				for(int j=0; j<10; j++) {
					int temp = changeNum(num,i,j);
					if(temp>=1000 && prime[temp]) {
						qu.offer(new int[] {temp,cnt+1});
					}
				}
			}
		}//while
		
		if(count == -1)
			System.out.println("Impossible");
		else
			System.out.println(count);
		
	}
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		int size = sc.nextInt();
		
		prime = new boolean[10000]; //소수인지 아닌지 일단 구하기
		
		//1000부터 10000까지 소수인지 아닌지 찾아서 boolean
		for(int i=1000; i<10000; i++) {
			prime[i] = isPrime(i);
		}
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		for(int i=0; i<size; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			bfs(start, end);
		}
	}
}

//참고 블로그 https://pangsblog.tistory.com/31

후기 (2h)

  1. 소수인지 아닌지도 찾아야하고
  2. 소수 체크와 동시에 bfs로 end까지 최소 얼마만에 도착하는지 확인한다
  3. bfs 내에서, for문 두개로 1000의 자리부터 숫자 바꿔보면서 (chaneNum함수)로
  4. 바꾼 숫자 temp가 1000을 넘으면서, 소수이면 queue에 넣어준다


넘 어렵….