[BOJ] 백준 1963번 소수 경로 (Java)

#1963 소수 경로

난이도 : 골드 4

유형 : 그래프/ BFS/ 에라토스테네스의 체 (소수)

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을 출력한다.

 

 

 

문제 풀이  

0~9의 숫자를 가지는 네 개의 정점을 특정 조건(소수)을 만족하는 경우에만 탐색하여 원하는 목적지로 가는 최단 경로를 구하는 문제이다. 해당 문제는 소수 찾기(에라토스테네스의 체)를 잘 모르면 헤맬 수 있으니 미리 공부하고오자!

 

📚 조건

   ∙ 비밀번호 4자리는 1000이상이다 (0039 x)

   ∙ 주어진 두 소수 A에서 B로 바꾸는 과정에서 네자리 소수를 항상 유지해야 한다.

 

 

흔히 자전거 탈 때 사용했던 자물쇠를 생각하면 된다.

 

ex) 초기값으로 0000이 되어있는 네개의 칸이 있으면 그것을 한 방향으로 돌려서 자신이 설정한 비밀번호(8012)로 이동해야 한다.

* 문제의 조건에 맞게 한 칸을 설정하는 데 한 번의 움직임을 사용한다고 하자.

 

1) 첫 번째 칸 : 0 →8 로 움직인다.  (움직임 +1)

2) 두 번째 칸 : 0  → 0 제자리 그대로 냅둔다.

3) 세 번째 칸 : 0 → 1 로 움직인다. (움직임 +1)

4) 네 번째 칸 : 0 → 2 로 움직인다. (움직임 +1) 

 

☛ 그래서 총 최소로 걸린 움직임은 3이다.

 

 

이제 이 방식에 소수를 얹기만 하면 된다. 자물쇠를 한 칸씩 조절하는데 그 네 개의 숫자 조합이 소수인 경우에만 멈추는 것이 가능하다.

 

그런데 막상 아무것도 없이 감으로 소수를 찾기에는 어려울 테지만...

만약 눈 앞에 소수가 모두 적힌 표가 있다면? 식은 죽 먹기일 것이다.

 

 

소수 찾기 1. 특정 숫자(num) 소수 판별하기

static boolean checkPrime(int num) {
	for(int i=2; i*i<=num; i++) {
		if(num%i ==0) {
			return false;
		}
	}
	return true;
}

 

 

소수 찾기 2. 10000이하의 소수 모두 찾기

static void checkPrime() {
	for(int i=2; i<10000; i++) {
		if(!isNotPrime[i]) {
			for(int j=i*i; j<10000; j+=i) {
				isNotPrime[j] = true;
			}	
		}
	}
}

 

☛ 매 연산마다 소수를 찾던가 아니면 미리 다 찾아놓고 대입해보던가 기호에 맞게 사용하면 된다. 그래도 탐색마다 연산을 계속하기 보다는 이미 범위가 주어졌기 때문에 미리 탐색을 다 해놓고 대입만 하면 되는 후자의 방법(10000이하의 소수 모두 찾기)을 더 권장한다.

 

 

풀이 코드  

이제 이 두 개의 과정을 합쳐 BFS탐색으로 설계만 잘하면 끝이다. 그리고 당연한 말이지만 가능하면 데이터를 다룰 때 String을 사용하지 않고 int값으로 다루는게 좋다.

 

 ☛ 나도 예전에 가끔 String이 더 다루기 편해서 String이나 char로 데이터 처리를 했었다가 성능을 꽤나 깎아먹었던 기억이 있다. int로 표현하면 2,147,483,647까지 4Byte로 표현되는데 String은 4자리 숫자 1234만 해도 한 칸당 2byte로 8byte를 잡아먹게 된다. 이런 문제는 그나마 다행이지 permutation 순열같은 로직에 String으로 데이터를 다루다가 허리가 휠 것이다.

 

 

그리고 boolean[]으로 방문 여부를 체크해주면 되는데 최근에 Map을 재밌게 다룬 기억이 있어서 또 사용해봤다. ☺️

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

public class Main {

	static boolean[] isNotPrime = new boolean[100001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine());
		checkPrime();
		
		StringTokenizer st= null;
		for(int i=0; i<t; i++) {
			st = new StringTokenizer(br.readLine());
			int src = Integer.parseInt(st.nextToken());
			int answer = Integer.parseInt(st.nextToken());
			
			sb.append(bfs(src,answer)+"\n");
		}
		System.out.println(sb.toString());
		
	}
	
	static String bfs(int src, int answer) {
		Queue<Integer> q = new LinkedList<>();
		Map<Integer, Integer> map = new HashMap<>();
		
		map.put(src,0);
		q.add(src);
		
		while(!q.isEmpty()) {
			int pos = q.poll();
			int move = map.get(pos);
			
			if(pos == answer) {
				return move+"";
			}
			
			int[] pNum = {pos/1000, (pos/100)%10, (pos/10)%10, pos%10}; 
			for(int i=0; i<4; i++) {
				for(int j=0; j<10; j++) {
					if(i==0 && j==0) continue; // 1000이상 
					
					int tmp = pNum[i];
					pNum[i] = j;
					int next = changePassword(pNum);
					pNum[i] = tmp;
					
					if(isNotPrime[next]) continue;
					
					if(!map.containsKey(next)) {
						q.add(next);
						map.put(next, move+1);
					}
				}
			}
		}
		
		return "Impossible";
	}
	
	static int changePassword(int[] pNum) {
		int num =0;
		for(int i=0; i<4; i++) {
			num += pNum[i]*(Math.pow(10, 3-i));
		}
		return num;
		
	}
	
	static void checkPrime() {
		for(int i=2; i<10000; i++) {
			if(!isNotPrime[i]) {
				for(int j=i*i; j<10000; j+=i) {
					isNotPrime[j] = true;
				}	
			}
			
		}
	}
}