백트래킹 예제

백트래킹이 도저히 이해가 안되서 예제 한문제 강의를 열번정도 돌려보고
코드를 그대로 따라쳐서 디버깅 모드로 하나씩 까보고있다.

예제는 5지선다의 정답이 주어지고,문제를 찍어서 풀때 5점 이상 받을 경우의 수를 구하는 것이다.

백트래킹이 돌아가려면 재귀함수나 다른 방법으로 푼다고 했는데, 다른방법은 기억안남.

여하튼 강사님도 재귀함수로 푸시니 재귀함수로 푸는 방법을 찾아보면, 코드를 유출해도 되나 모르겠다;

문제 갯수가 numOfProblems.

solution 메소드에서 초기값 넣어서 백트래킹 메소드 호출.

백트래킹 메소드에서는 조건에 맞게 설계.

5지선다니까 1~5 for문을 돌린다.
제출한 답안지 배열 현재 idx에 1~5까지 차례로 넣는다.
차례로 넣을때 답이 맞으면 correctCnt, idx를 하나씩 올려서 넘긴다.
답이 안맞으면 idx만 올려서 넘긴다.

끝날때까지 무한반복인데, 이해가 안되었던게, 5점이상인 경우를 한번 만들고 나면 다시 돌아가서 모든 경우를 다 확인할 수 있는게 이해가 좀 안된다..

노트에 쓰고싶지만 지금은 노트가 없다 하하

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class BackTrackingEX_오지선다 {
    final static int numOfProblems = 10;
    static int cnt;

    public static void solution(int[] sols){
        if (sols==null || sols.length != numOfProblems){
            return;
        }

        cnt = 0;
        int[] submit = new int[numOfProblems];
        // backTracking
        backTracking(sols, submit,0,0);
        System.out.println(cnt);
    }

    public static void backTracking(int[] sols, int[] submit, int correctCnt, int idx){
        //뒤에꺼를 다 맞아도 5점이상이 안되는 경우.
        if (numOfProblems - idx +correctCnt<5){
            return;
        }
        if (idx == numOfProblems){
            if (correctCnt >= 5){
                cnt += 1;
            }
        }else{
            int twoInRow = 0;
            if (idx >=2){
                if (submit[idx-1] == submit[idx-2]){
                    twoInRow = submit[idx-1];
                }
            }

            for (int i = 1; i <= 5; i++) {
                if (i == twoInRow){
                    continue;
                }

                submit[idx] = i;
                if (sols[idx] == i){
                    backTracking(sols, submit, correctCnt+1, idx+1);
                }else{
                    backTracking(sols, submit,correctCnt,idx+1);
                }
                submit[idx] = 0;
            }
        }

    }

    public static void main(String[] args) throws Exception {
        int[] sols = {1,2,3,4,5,1,2,3,4,5};
        solution(sols);

        sols = new int[] {1,1,2,2,3,3,4,4,5,5};
        solution(sols);
    }


}