[알고리즘] 백트래킹이란? & 대표 문제: 백준 15679 N과M(1) - 자바

✔️ 백트래킹이란?

백트래킹이란?
해를 찾는 도중에 막히면 더이상 탐색하지 않고, 이전 단계로 되돌아가서(재귀) 해를 찾아나가는 기법을 의미한다.

출처 : https://goldenrabbit.co.kr/2023

 

백트래킹은 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다. 

이처럼 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning) 이라고 한다.

 

따라서, 백트래킹은 모든 노드를 DFS를 통해 탐색하면서 더 이상 필요가 없는 부분을 쳐내는 가지치기(pruning)를 하는 것이다.

 

 

DFS 완전탐색으로 경우의 수를 찾아야할 경우, 불필요한 탐색을 건너뛸 여지가 있다면 백트래킹을 이용할 수 있다. !!

---

✔️ 대표적인 문제 예시 : 백준 15649 - N과 M(1)

문제 바로 가기 : https://www.acmicpc.net/problem/15649

 

• arr : 출력할 수열을 담을 배열
• visited : 중복되지 않은 수를 출력하기 위해 방문 여부를 담을 배열

import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.io.InputStreamReader;

public class Main{
    static int[] arr;
    static boolean[] visited;
    private static StringBuilder result = 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까지의 수
        int n = Integer.parseInt(st.nextToken());
        //m 길이 만큼
        int m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        visited = new boolean[n];
        dfs(n,m,0);
        System.out.println(result);
        }

    public static void dfs(int n, int m, int depth) {

        if(depth == m){
            for(int i  = 0; i<m; i++){
                result.append(arr[i]).append(' ');
            }
            result.append('\n');
            return;
        }

        for(int i = 0; i< n; i++){
            //해당 노드를 방문 하지 않았다면
            if(!visited[i]){
                visited[i] = true; //(= 같은 수를 출력하지 않기 위함 ex. 1,1)
                arr[depth] = i+1;
                dfs(n,m, depth+1);

                visited[i] = false;
            }
        }
    }


}

 

재귀 함수가 어떤 식으로 돌아가는지 손으로 써보면 이해하기 쉽다 !!