[BOJ] 1963. 소수 경로 - Java

앞으로 백준문제를 풀면서 새로 배운 내용이나 기억해야 할 내용에 대해 적어보려고 한다.

1963 소수경로 - (https://www.acmicpc.net/problem/1963)

• 접근

  브루트포스(Brute Force)와 관련된 문제이다. 소수인 a와 b를 입력받고 최소한의 횟수로 숫자(소수만 가능)를 변경해 a에서 b에 도달해야하는지 도출해내는 문제다.

• 풀이

  처음에는 예제를 보면서 일련의 규칙이 있는지 확인했지만, 규칙을 발견하지 못해 모든 경우의 수를 따져보는 쪽으로 접근했다. 4자리 수의 소수로만 변경이 가능해 먼저 에라토스테네스의 체로 소수를 판별했다.

 static void sieveOfEratosthenes() {
		// false면 소수
        isPrime[0] = isPrime[1] = true;
        for (int i = 2; i * i < 10000; i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j < 10000; j += i)
                    isPrime[j] = true;
            }
        }
    }

그리고 모든 경우의 수를 확인하고 최단거리로 최소횟수를 구해야 하므로 BFS를 떠올렸다.

static void bfs(int val) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(val);
        while (!q.isEmpty()) {
            Integer poll = q.poll();
            visited[poll] = true;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j <= 9; j++) {
                    if (i == 0 && j == 0) {
                        continue;
                    }
                    if (step[b] > 0) {
                        System.out.println(step[b]);
                        return;
                    }
                    Integer changeNum = changeNum(i, j, poll);
//                    System.out.println(changeNum);
                    if (!isPrime[changeNum] && !visited[changeNum]) {
                        visited[changeNum] = true;
                        step[changeNum] = step[poll] + 1;
                        q.offer(changeNum);
                    }
                }
            }
        }
    }

int형으로 입력받은 숫자의 특정 자릿 수를 어떻게 변경할 수 있을까?

StringBuilder

setCharAt(): 문자열 중에서 특정 위치에 있는 문자열의 값을 교체하는 메서드

StringBuilder sb = new StringBuilder(String.valueOf(num));
sb.setCharAt(i, (char)(j + '0'));

StringBuilder에서 setChar()로 간단하게 String index의 값을 변경할 수 있다.

• 결론

  이 문제를 풀려면 3개의 정보를 알고 있어야 했다.
  1. 에라토스테네스의 체
  2. BFS
  3. StringBuilder -> setChar()