2 - 4. Back Tracking 예제 (3671번: 산업 스파이의 편지)

백준 3671번(산업 스파이의 편지)

저번에 잠깐 설명했던 백트래킹 문제를 하나 가져왔습니다.

(열심히 썼으니... 아직 잘 모르시겠다면, 여기를 참고해주세요.)

소수를 이용하네요. 범위는 7자리니까 1 ~ 9,999,999까지 나옵니다.

테스트 케이스가 최대 200개이고, 따라서 그냥 막 접근하면 시간초과가 나겠죠.

우선 소수를 빠르게 구할 수 있는 에라토스테네스의 체(Eratosthenes's sieve) 알고리즘부터 공부해보시는게 좋습니다.

수학 관련 알고리즘을 다룰건 아니니까 자세한 설명은 생략하겠습니다. 아래 링크를 참고해주세요.

(wiki: 에라토스테네스의 체)

우선적으로 테스트케이스를 여러번 돌려야하니까 미리 반복문 밖에서 소수를 최댓값(9,999,999)까지 구해둡니다.

그리고 다음으로 백트래킹을 이용해서 탐색하는데, 숫자가 몇자리 주어지고 이를 통해서 만들 수 있는 소수의 수를 찾아야합니다.

종이는 중복으로 사용은 불가하지만, 가지고 있는 것 중에서 제외시키고 구성하는 것은 가능합니다.

이정도만 확인하고 넘어가면 될 것 같습니다.

그리고 우리는 정해진 숫자로 재배치만 하면 되는 것이니, 1 ~ 9,999,999까지 하나씩 반복문을 돌려 볼 필요도 없겠네요.

결국 지난번 설명했던 'N과 M'이라는 문제와 매우 유사합니다.

다른점은 주어진 숫자를 모두 사용할 필요가 없다는 것, 그리고 소수인지 판별해야하는 것, 두 가지네요.

그 외에는 진짜 너무 다 똑같기 때문에 따로 드릴 설명은 없을 것 같아요.

(이전 포스팅 보시고 그래도 이해 안되신다면, 댓글 달아주세요. 같이 고민해보겠습니다.)

prime: 인덱스에 해당하는 수가 소수라면 true 값을 가집니다.

used: 주어진 테스트 케이스의 i번째 숫자가 사용 중인지 표시 해줍니다. (즉, 34218의 i == 1 이면 4가 됩니다.)

list: 중복 방문을 위해 이미 찾은 소수는 소수 배열에서 false로 바꿔주는데요. 

이 소수를 탐색이 끝난 후 다시 true로 바꾸기 위해 사용합니다.

3671번 전체 코드

package back_tracking;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
 
/**
 * 
 *     @author minchoba
 *    백준 3671번: 산업 스파이의 편지
 *
 *    @see https://www.acmicpc.net/problem/3671/
 *
 */
public class Boj3671 {
    private static boolean[] isPrime = new boolean[10_000_000];
    private static LinkedList<Integer> list = new LinkedList<>();
    private static int count;
    
    private static final char NEW_LINE = '\n';
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int c = Integer.parseInt(br.readLine());
        
        prime();                        // 소수 찾기
        
        while(c-- > 0) {
            char[] paper = br.readLine().toCharArray();
            count = 0;
            
            for(int i = 0; i < paper.length; i++) {
                boolean[] used = new boolean[paper.length];
                backTracking(i, paper[i] + "", paper, used);
            }
            
            while(!list.isEmpty()) {        // 탐색시 false가 된 소숫값을 다시 true로 변경
                int num = list.remove();
                isPrime[num] = true;
            }
            
            sb.append(count).append(NEW_LINE);
        }
        
        System.out.println(sb);        // 결과 출력
    }
    
    private static void prime() {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for(int i = 2; i < isPrime.length; i++) {            // 에라토스테네스의 체
            if(!isPrime[i]) continue;
            
            for(int j = i + i; j < isPrime.length; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    private static void backTracking(int idx, String current, char[] arr, boolean[] used) {
        if(current.length() > arr.length) return;        // 길이가 주어진 문자열보다 길어진 경우
        int num = Integer.parseInt(current);
        
        used[idx] = true;
 
        if(isPrime[num]) {            // 확인된 소수를 배열에서 제거하고 리스트에 임시 저장
            list.add(num);
            
            isPrime[num] = false;
            count++;
        }
        
        for(int i = 0; i < arr.length; i++) {            
            if(used[i]) continue;                // 이미 사용된 숫자인 경우
            
            String next = current + arr[i];
            backTracking(i, next, arr, used);    // 다음으로 생성된 문자열로 재귀 탐색
            used[i] = false;                    // 백트래킹
        }
    }
}
 

달라진 점은 소수를 찾았을 때 소수가 아님으로 초기화해주고, 리스트에 그 값을 담는 정도입니다.

그리고 이전 예제와 같이 주어진 숫자들로 순열을 생성하는데, 길이에 상관없이 소수면 모두 포함시킨다 정도 되겠네요.

문제 조건에 따라 앞에 0이 붙었을때 같은 수 즉, 2 또는 02, 002 .... 다 같은 수라고 했으니 정수로 변환시켜서 구분했구요.

정답율과 같이 크게 어려운 문제는 아닙니다.. ㅎㅎ

채점 결과

물론 저는 뭐.. 처음에 사용한 숫자를 초기화 안하고 뭐.. 여러가지로 실수가 좀 있었지만요.

이 문제의 경우엔 최악의 경우 자릿수 마다 모두 탐색해줘야 하고, 0 ~ 9까지 모두 들어올 수 있습니다.

따라서 시간 복잡도는 O(10^7) = 10_000_000 정도 되겠네요. (자릿수 7개마다 가능한 숫자 10개)

이해안가는 것이나, 질문 또는 잘못된 부분은 댓글로 지적 부탁드려요. 감사합니다.

문제의 저작권은 백준 온라인 저지에 있습니다.