[BOJ] 1963 java

문제

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

 

풀이

primeNum(int size): size까지의 소수 목록 -> fillPrimeArr()로 처음 1번 생성

 

tc입력 -> tc만큼 아래 로직 반복

1. start, target 소수 입력
2. bfs(): start에서 target으로 만드는 데에 필요한 횟수 반환
   1. queue.poll()이 target과 같으면 횟수 반환
   2. getNext(): queue.poll()로 꺼낸 수에서 한 자릿수를 변경한 수의 list 반환
   3. list의 수 중 방문했거나 소수가 아닌 수는 queue에 넣을 수 없음

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static boolean[] primeNum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 줄에 test case의 수 T가 주어진다.
        int tc = Integer.parseInt(br.readLine());
        // 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
        fillPrimeArr(9999);

        while(tc-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());

            // [solution] start->target
            int cnt = bfs(start, target);
            // cnt가 -1이면 Impossible, 아니면 cnt 출력
            System.out.println((cnt==-1)? "Impossible" : cnt);
        }
        br.close();
    }

    public static void fillPrimeArr(int size){
        primeNum = new boolean[size+1];
        Arrays.fill(primeNum, true);
        for (int i = 2; i <= size; i++) {
            if(!primeNum[i]) continue;
            for (int j = i*i; j <= size; j+=i) {
                primeNum[j]=false;
            }
        }
    }

    public static int bfs(int start, int target) {
        Queue<Pair> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[10000]; // 4자리 소수

        queue.offer(new Pair(start, 0));
        visited[start] = true;

        while (!queue.isEmpty()){
            Pair curr = queue.poll();

            // [return1] target과 같으면 cnt 반환
            if(curr.num==target) return curr.cnt;

            // nextNumbers: 1자리 수만 변경한 수들 모임
            String num = String.valueOf(curr.num);
            List<Integer> nextNumbers = getNext(num);
            for (int next : nextNumbers) {
                // 소수가 아님 || 이미 방문한 수
                if(!primeNum[next] || visited[next]) continue;

                queue.offer(new Pair(next, curr.cnt+1));
                visited[next]=true;
            }
        }

        // [return2] 불가능한 경우
        return -1;
    }

    // num에서 1자릿수만 변경한 수들 리스트 반환
    private static List<Integer> getNext(String num) {
        List<Integer> nextNumbers = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 10; j++) {
                // i번째 자릿수를 j로 변경
                char[] tmp = num.toCharArray();
                tmp[i]= (char) (j + '0');

                int next = Integer.parseInt(new String(tmp));

                // 숫자가 4자리인지 확인
                if (next < 1000 || next > 9999) continue;

                nextNumbers.add(next);
            }
        }
        return nextNumbers;
    }

    public static class Pair {
        int num;
        int cnt;

        public Pair(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}

 

nextNumbers 생성할 때 생긴 문제들

1033이 queue.poll()로 나오게 된다면 nextNumbers에는 아래와 같이 값이 담겨야 한다.

nextNumbers ={1030, 1031, 1032, 1033, 1034, 1035, 1036, 1037, 1038, 1039,
		1003, 1013, 1023, 1033, 1043, 1053, 1063, 1073, 1083, 1093,
		1033, 1133, 1233, 1333, 1433, 1533, 1633, 1733, 1833, 1933,
		0033, 1033, 2033, 3033, 4033, 5033, 6033, 7033, 8033, 9033}

 

[시도1] num+Math.pow(10, i) *j

이렇게 하니까 1034+6 = 1040이 됨 -> 원하는 것은 이게 아님

int num = curr.num;
List<Integer> nextNumbers = new ArrayList<>();
for (int i = 0; i < 4; i++) {
	for (int j = 1; j < 10; j++) {
		int next = (int) (num + Math.pow(10, i)*j);
		nextNumbers.add(next);
	}
}

 

[시도2] String, charAt() 이용 -> 에러남

String num = String.valueOf(curr.num);
List<Integer> nextNumbers = new ArrayList<>();
for (int i = 0; i < 4; i++) {
	for (int j = 1; j < 10; j++) {
		String next = num;
		next.charAt(i) = next.charAt(i) + (char)j;
	}
}