[백준] 1963번 소수 경로 Java

문제 링크

https://www.acmicpc.net/problem/1963

알고리즘: BFS, 에라토스테네스의 체

문제

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

“이제 슬슬 비번 바꿀 때도 됐잖아”
“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
“그럼 8179로 해”
“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
“귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

풀이

1. 먼저 10000 크기의 bool 배열을 생성해준다. => 네 자리 소수이기 때문에
2. 소수값을 가진 인덱스를 표시해준다. true or false로
3. BFS를 실행하는데 Queue에는 중복이 아니면서, 소수 값만을 넣어주고 탐색을 진행한다.
4. 목푯값이 나왔다면 count 값을 리턴해준다.

소스 코드

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

class Node {
    int v,c;
    Node(int v, int c) {
        this.v = v;
        this.c = c;
    }
}

public class Main {
    static boolean nDecimal[] = new boolean[10000];
    static int T;
    static String ans;
    public static void main(String args[]) throws IOException {
      nDecimal[0] = true;
      nDecimal[1] = true;
      for(int i=2; i*i<=9999; i++) {
          for(int j=i*i; j<=9999; j+=i) {
              nDecimal[j] = true;
          }
      }
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      T = Integer.parseInt(br.readLine());
      ans = "";
      for(int i=0; i<T; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int s = Integer.parseInt(st.nextToken());
          int e = Integer.parseInt(st.nextToken());
          boolean clone_nDecimal[] = nDecimal.clone();
          int result = BFS(s,e,clone_nDecimal);
          if(result == -1) {
              ans += "Impossible\n";
          } else {
              ans += Integer.toString(result) + "\n";
          }
      }
      System.out.println(ans.trim());
    }
    static int BFS(int start,int end, boolean nDec[]) {
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(start, 0));
        nDec[start] = true;
        while(!que.isEmpty()) {
            Node n = que.poll();
            if(n.v == end) {
                return n.c;
            }
            for(int i=0; i<4; i++) {
                for(int j=0; j<=9; j++) {
                    //첫째 자리는 0빼고
                    int nv = 0;
                    if(i==0) {
                        if(j!=0) {
                            nv = j * 1000 + n.v % 1000;
                        }
                    } else if(i==1) {
                        nv = n.v/1000 * 1000 + j * 100 + n.v % 100;
                    } else if(i==2) {
                        nv = n.v/100 * 100 + j * 10 + n.v % 10;
                    } else {
                        nv = n.v/10 * 10 + j;
                    }
                    if(!nDec[nv]) {
                        nDec[nv] = true;
                        que.add(new Node(nv, n.c+1));
                    }
                }
            }
            
        }
        return -1;
    }
}