[Java] 백준 1963번 : 소수 경로

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 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

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int T;
	private static String from, to;

	static class Number {	// 현재 비밀번호, 현재 비밀번호까지 변경 횟수
		String from;
		int cnt;

		public Number(String from, int cnt) {
			super();
			this.from = from;
			this.cnt = cnt;
		}

		@Override
		public String toString() {
			return "Number [from=" + from + ", cnt=" + cnt + "]";
		}
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		T=Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			st=new StringTokenizer(br.readLine());
			from=st.nextToken();
			to=st.nextToken();
			int result=bfs();	// bfs를 돌며 from에서 to까지 변환이 가능한지 확인
			if(result==-1) System.out.println("Impossible");	// -1이면 변환 불가능
			else System.out.println(result);	// -1이 아니면 가능한 횟수 출력
		}
	}

	private static int bfs() {	// 4자리 중 한 자리씩 변경하며 bfs를 통해 가능한 횟수 구하기
		Queue<Number> queue=new LinkedList<>();
		queue.add(new Number(from, 0));
		
		boolean []visited=new boolean[10000];
		visited[Integer.parseInt(from)]=true;
		
		while(!queue.isEmpty()) {
			int size=queue.size();
			while(size-->0) {
				Number n=queue.poll();
				
				if(n.from.equals(to)) return n.cnt;
				for(int i=0;i<4;i++) {
					for(int j=0;j<=9;j++) {
						if(j==0 && i==0) continue;	// 0으로 시작하는 수는 불가능
						String s=n.from.substring(0, i)+(j+"");
						if(i<3) s+=n.from.substring(i+1);
						if(isPrime(s) && !visited[Integer.parseInt(s)]) {	// 한 자리 변환한 수가 소수이고, 아직 방문하지 않은 경우, 방문 처리 후 큐에 넣어줌
							visited[Integer.parseInt(s)]=true;
							queue.add(new Number(s, n.cnt+1));
						}
					}
				}
			}
		}
		
		return -1;
	}
	
	private static boolean isPrime(String s) {	// 소수 여부 확인
		int num=Integer.parseInt(s);
		for(int i=2;i<=(int)Math.sqrt(num);i++) {
			if(num%i==0) return false;
		}
		return true;
	}
}

1. 시작 비밀번호와 목표 비밀번호를 각각 문자열로 입력받습니다.

2. (현재 비밀번호, 현재 비밀번호까지 변경한 횟수) 를 저장할 클래스 Number를 만듭니다.

3. 소수인지 여부를 판별할 isPrime 메서드를 만듭니다.

4. bfs를 통해 큐에 Number를 넣어가며 목표 비밀번호까지 도달 가능한 최소 횟수를 구합니다.

    4-1. 한 자리 변경한 현재 숫자가 목표 비밀번호와 일치하면 횟수를 리턴합니다.

    4-2. 한 자리 변경한 현재 숫자가 0으로 시작하면 다음으로 넘어갑니다.

    4-3. 한 자리 변경한 현재 숫자가 소수이고, 아직 방문하지 않은 경우, 방문 처리 후 큐에 넣어줍니다.