[JAVA] 백트래킹(완전탐색) + 백준 #15649 N과 M(1)

백트래킹이란

해를 찾는 도중 해가 아니라서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다. (완전탐색 중 한가지)

DFS

• 백트래킹은 DFS(깊이우선탐색)와 BFS(너비우선탐색) 중 DFS 기법을 주로 사용한다.

=> 두 가지 모두 사용가능하지만 해를 찾지 못하면 다시 되돌아가서 해를 찾아야하므로 쉽게 되돌아갈 수 있는 방법인 DFS를 많이 사용한다.

백트래킹 예시

백준 #15649 N과 M(1)

문제

• 자연수 n,m이 주어졌을 때, 1~n까지의 자연수 중에서 중복 없이 m개를 고른 수열을 모두 구하기

입력

4 2

출력

• 한 줄에 하나씩 조건을 만족하는 수열 출력
• 중복 수열은 한번만 출력
• 각 수열은 공백으로 구분해서 출력
• 사전 순으로 증가하는 순서로 출력

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

백트래킹 알고리즘 사용 이유

• n개 중에 m개를 선택하는 것이므로 완전탐색을 해야 한다.
• 중복을 방지하고 특정 순서를 유지하면서 선택해야 하는 문제로 순열을 생성하기에는 백트래킹이 적합하다.

전체 코드

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

public class Main {
    static boolean[] visited; //방문 배열(중복X)
    static int[] arr; //수열
    static int n,m;
    static StringBuilder sb = new StringBuilder();

    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());
        visited = new boolean[n+1];
        arr = new int[m];
        dfs(0);
        System.out.println(sb);
    }
    public static void dfs(int d) { //DFS 함수 생성
        if(d == m) { //깊이가 m과 같다면 내용 출력
            for(int x : arr) {
                sb.append(x).append(" ");
            }
            sb.append("\n");
            return; //출력 후 이 함수 종료
        }
        for(int i=1; i<=n; i++) {
            if(!visited[i]) { //방문하지 않았다면
                visited[i] = true;
                arr[d] = i; //수열에 추가
                dfs(d+1); //다음 깊이로 재귀호출
                visited[i] = false; //다른 탐색을 위해 방문하지 않은 걸로 표시 바꾸기
            }
        }
    }
}