백트래킹 - 백준15649 N과 M(1)

백트래킹도 BFS와 마찬가지로 기본적인 틀이 있다고 한다. 명확하게 알려주는 곳은 없지만 내 나름대로 정리해보면 다음과 같다.

1. static boolean[] isUsed (사용 여부 표시 배열)
2. static int[] answer (정답 기록 배열)
3. 백트래킹 재귀함수 실행
   3-1. argument : 선택 범위 중, 현재까지 선택된 범위 (0부터 시작)
   3-2. boundary condition (현재까지 선택된 범위가 선택 범위의 마지막이면 return)
   3-3. 탐색 범위 순회 반복문
   3-3 -1. if(사용중인 곳이면) continue
   3-3 -2. answer 배열의 현재 범위에 사용
   3-3 -3. isUsed배열에 사용여부 표시
   3-3 -4. 재귀함수호출(argument로 다음 선택 범위)
   3-3 -5. isUsed배열에 사용여부 표시 제거

이를 본 문제의 코드에 적용하면 다음과 같다.

import java.io.*;
import java.util.*;

class Main{
    
    static int n;
    static int m;
    static boolean[] isUsed = new boolean[8];	//사용 여부 표시 배열
    static int[] answer = new int[8];	//정답 기록 배열
    
    static{
        for(int i = 0; i < 8; i++){
            isUsed[i] = false;
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        solve(0);	//백트래킹 재귀함수 실행
    }
    
    static void solve(int now){
    //argument : 선택 범위 중, 현재까지 선택된 범위 (0부터 시작)
    
    	//boundary condition (현재까지 선택된 범위 now가 선택 범위의 마지막 m이면 return)
        if(now == m){
            for(int i = 0; i < m; i++){
                System.out.print(answer[i] + " ");
            }
            System.out.println();
            return;
        }
        
        //탐색 범위 순회 반복문
        for(int i = 1; i <= n; i++){
        
        	//if(사용중인 곳이면) continue
            if(isUsed[i-1] == true){
                continue;
            }
            //answer 배열의 현재 범위에 사용
            //isUsed배열에 사용여부 표시
            answer[now] = i;
            isUsed[i-1] = true;
            //재귀함수호출(argument로 다음 선택 범위)
            solve(now+1);
            //isUsed배열에 사용여부 표시 제거
            isUsed[i-1] = false;
        }
    }
}

* 이전 상태와 다음 상태를 기반으로 문제를 해결한다면 백트래킹
* 꼭 '깊이'나 '탐색'의 개념이 아니더라도, 모든 경우의 수를 다 대입해보는 것이면 브루트 포스

* 보통 백트래킹은 재귀 방식으로 문제를 해결

+ 원래 완전탐색 알고리즘인데, 여기에 조건 코드를 추가한게 이 백트래킹이라고 함
+ 순열, 조합, 부분집합(순조부) 구하기도 완전탐색에서 파생되는 패턴
+ 재귀함수 내부 코드 외우는 건 추천x, 생각해서 구현하기
(데브코스 중)
참고 : 순조부 문제에 대한 글

부분집합 팁 (또는 모든 element를 단, 한 번씩만 쓰는 경우)
재귀문 안에서 for()문을 돌 필요가 없음
-> for()문 빼고 그냥 "현재를 포함시키고 재귀호출, 현재를 포함하지 않은채로 재귀호출"
이렇게 두 번 하면 됨
예시 참고 - 문제풀이 예시 _백준 문제 링크