백트래킹 - 순열

순열

- n개의 원소를 가지는 배열에서 r개의 원소를 선택하여 나열하는 문제. 여기서는 n == r 로 가정하겠다.

조건

- 

풀이전략

(1) 선택된 원소의 인덱스를 표현하는 selectedIndex배열을 선언.

(2) selectedIndex의 인덱스를 0 ~ n-1까지 증가시키며 인덱스에 위치할 수 있는
    후보군 인덱스 배열을 구한다 (getCandidates)

(3) 선택된 인덱스에 반복문을 이용하여 후보군에서 구한 인덱스를 대입한다 
(4) 백트래킹을 실행한다. (2) ~ (3) 반복

구현하기

import java.util.ArrayList;
import java.util.List;
 
/**
 * n개의 원소를 가지는 배열의 모든 순열을 구하는 문제
 * @author troh
 *
 */
public class Stack백트래킹_순열 {
    // n개의 원소를 가지는 배열
    private static int[] arr = {1, 2, 3, 4};
    // 순열의 인덱스를 가리키는 배열
    private static int[] index = {-1, -1, -1, -1};
    
    public static void main(String[] args) {
        backTracking(index, -1, 3);
    }
    
    public static void backTracking(int[] selectedIndex, int k, int input) {
        // 결과 출력
        if(k == input) {
            System.out.printf("{");
            for(int i=0; i<=k; i++) {
                System.out.printf(" %d", arr[selectedIndex[i]]);
            }
            System.out.printf("}\n");
        } else {
            k++;
            /**
             * k인덱스에 대입할 수 있는 인덱스를 구하는 구함
             * 예를 들어 인덱스 0에는 { 0, 1, 2, 3} 
             * 모두 가능하지만 0번째 인덱스에 1을 선택했다면
             * 다음 인덱스 1에는 1을 제외한 {0, 2, 3}이 선택 가능함
             */
            int[] candidates = getCandidates(selectedIndex, k, input);
            for(int i=0; i<candidates.length; i++) {
                selectedIndex[k] = candidates[i];
                backTracking(selectedIndex, k, input);
            }
        }
    }
    
    /**
     * 현재까지 선택되지않은 순열 반환
     * @param a 현재까지 선택된 순열
     * @param k 배열의 최대 인덱스
     * @return
     */
    public static int[] getCandidates(int[] selectedIndex, int k, int input) {
        /**
         * 선택되지 않은 원소찾기
         */
        boolean[] selectedIndexCheck = new boolean[input+1];
        for(int i=0; i<k; i++) {
            selectedIndexCheck[selectedIndex[i]] = true;
        }
        
        /**
         * 선택되지않은 원소의 인덱스를 배열로 만들어서 반환
         */
        int[] nonSelectedIndex = new int[input-k+1];
        int tempIndex = 0;
        for(int i=0; i<input+1; i++) {
            if(selectedIndexCheck[i] == false) {
                nonSelectedIndex[tempIndex] = i;
                tempIndex++;
            }
        }
        return nonSelectedIndex;
    }
}