완전탐색(브루트 포스), 백트래킹

https://school.programmers.co.kr/learn/courses/30/lessons/258709

프로그래머스

 

A가 고를 주사위의 총 경우의 수 구하기 < - 완전탐색

 

 static int n;
 static boolean[] visited;
 static List<int[]> diceComb;


static void permutation(int depth, int index, int[] arr) {
        if (depth == n / 2) {
            diceComb.add(arr.clone());   //깊은 복사 
            return;
        }

        for (int i = index; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i;   // 배열 덮어쓰기
                permutation(depth + 1, i + 1, arr);
                visited[i] = false;
            }
        }
    }

코드 출처: https://school.programmers.co.kr/questions/66170?referer=collection-of-questions

 

• diceComb.add(arr.clone())        깊은 복사/ arr의 값이 바껴도 diceComb에 담긴 arr에 요소들의 값은 바뀌지 않는다.
• 파라미터에 있는 index는  중복된 ([2,4] [4,2]) 요소들을 배제하기 위해 존재하는 파라미터이다.
  • 첫 번째에 4를 선택한다면 두 번째에는 5이상 숫자부터 탐색한다. 2(4보다 낮은 수)를 선택하지 못한다. 
• 함수 시작에 함수 종료 조건과 종료와 동시에 원하는 행위 명시
• 재귀함수 호출은 자식 노드로 내려가기 위함이다. 쉽게 말하면 총 4개의 주사위를 뽑아야 할 때, 3번째에서 4번째 주사위를 고르는 행위로 넘어가는 것이다.
• for문은 인접 자식노드로 이동하기 위함이다. 쉽게 말하면 4번째에 올 수 있는 다른 주사위를 고르는 행위이다.