백트래킹 구현

자료구조 구현

백트래킹 구현

lipnus 2019. 4. 3. 23:03

백트리킹을 재귀를 이용해서 3가지 방법으로 구현

3칸에 1~4를 중복해서 넣어서 나오는 경우의 수

3번째 방법이 가장 간결한 것 같다.

package 테스트;


import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {


        //재귀 첫번째
        for(int i=1; i<=4; i++){
            recur1(0, new int[3], i);
        }

        System.out.println();

        //재귀 두번째
        for(int i=1; i<=4; i++){
            int[] arr = new int[3];
            arr[0] = i;
            recur2(1, arr);
        }

        System.out.println();

        //재귀 세번째
        for(int i=1; i<=4; i++){
            Stack<Integer> s = new Stack<>();
            s.add(i);
            recur3(0, s);
            s.pop();
        }
    }



    static void recur1(int n, int[] arr, int target){

        arr[n] = target;

        if(n==2){
            print(arr);
            return;
        }

        for(int i=1; i<=4; i++){
            recur1(n+1, arr, i);
        }
    }



    static void recur2(int n, int[] arr){

        if(n==3){
            print(arr);
            return;
        }

        for(int i=1; i<=4; i++){
            arr[n]=i;
            recur2(n+1, arr);
        }
    }


    static void recur3(int n, Stack<Integer> s){

        if(n==2){
            print(s);
            return;
        }

        for(int i=1; i<=4; i++){
            s.add(i);
            recur3(n+1, s);
            s.pop();
        }


    }



    static void print(int[] arr){
        for(int a: arr){
            System.out.printf("%d " , a);
        }
        System.out.println();
    }

    static void print(List<Integer> list){
        for(int a: list){
            System.out.printf("%d " , a);
        }
        System.out.println();
    }


}

1 1 1

1 1 2

1 1 3

1 1 4

1 2 1

1 2 2

1 2 3

1 2 4

1 3 1

1 3 2

1 3 3

1 3 4

1 4 1

1 4 2

1 4 3

1 4 4

2 1 1

2 1 2

2 1 3

2 1 4

2 2 1

2 2 2

2 2 3

2 2 4

2 3 1

2 3 2

2 3 3

2 3 4

2 4 1

2 4 2

2 4 3

2 4 4

3 1 1

3 1 2

3 1 3

3 1 4

3 2 1

3 2 2

3 2 3

3 2 4

3 3 1

3 3 2

3 3 3

3 3 4

3 4 1

3 4 2

3 4 3

3 4 4

4 1 1

4 1 2

4 1 3

4 1 4

4 2 1

4 2 2

4 2 3

4 2 4

4 3 1

4 3 2

4 3 3

4 3 4

4 4 1

4 4 2

4 4 3

4 4 4