[PS] 프로그래머스 - 삼총사 ( 백트래킹 ) with JAVA

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

프로그래머스

 

 

◎ 문제풀이

 

N명의 학생 중에 3명의 조합을 찾는 문제이다. 

 

조합의 모든 경우의 수를 완전탐색하는 알고리즘에는 백트래킹(BackTracking)이 있다. DFS와는 다르다. DFS는 모든 '노드'를 방문하는 완전탐색 시, 사용되는 알고리즘이다. 백트래킹은 모든 '조합'을 완전 탐색하는 경우 사용되는 알고리즘이다. 그럼 백트래킹을 사용하여 N명의 학생 중 3명의 조함(삼총사)를 찾는 코드를 구현해보자.

 

주의해야 할 점이 있다.

 

backtracking은 for문을 돌려 나올 수 있는 경우의 수마다 재귀호출을 해준다. 이때 for문의 범위를 이전 인덱스 이후 범위로 설정해야 한다. 

 

    public void backtracking(int index, int depth, int sum, int[] number){
		// 탈출조건 중략....
        
        for(int i=index;i<number.length;i++){ // index 부터 반복시작
		// 재귀호출 중략....
        }
    }

 

 

그 이유는 중복되는 경우가 생기기 때문이다. 

 

1 ~ 6 의 수 중에서 1,3,6 을 선택하는 탐색을 보자. 만약 for문의 i 시작점을 0으로 고정한다면 동일한 조합을 중복해서 탐색하게 된다.

 

    public void backtracking(int index, int depth, int sum, int[] number){
		// 탈출조건 중략....
        
        for(int i=0;i<number.length;i++){ // index 부터 반복시작
		// 재귀호출 중략....
        }
    }

 

 

재귀호출의 첫 시작점이 1인 경우, 3인 경우, 6인 경우 모두 1,3,6 을 탐색할 수 있다. 

 

 

 

 

이와 같이 동일한 조합을 중복 탐색하는 경우를 방지하려면 이전에 탐색했던 index 보다 큰 범위에서만 탐색을 하도록 해야 한다. 

 

 

◎ 코드

class Solution {
    
    public int answer;
    public boolean[] visited;
    
    public int solution(int[] number) {
        visited = new boolean[number.length];
        backtracking(0,0,0,number);
        return answer;
    }
    
    
    public void backtracking(int index, int depth, int sum, int[] number){
        if(depth == 3){
            if(sum == 0) {
                for(int i=0;i<visited.length;i++){
                    System.out.print(visited[i]+ " ");
                }
                answer++;
            }
            return;
        }
        
        for(int i=index;i<number.length;i++){
            if(!visited[i]){
                visited[i] = true;
                backtracking(i+1,depth+1,sum+number[i],number);
                visited[i] = false;
            }
        }
    }
}