[java백준/백트래킹]실버 3/ 15649번 N과 M(1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n, m;
    public static int[] arr;
 
    public static boolean visited[];
 
    public static void DFS(int depth) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        } else {
            for (int i = 1; i <= n; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    arr[depth] = i;
                    DFS(depth + 1);
                    visited[i] = false; //리턴하면서 원래 true였던 애들 다시 false로 돌려줘야 
                }
            }
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
 
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        visited = new boolean[n + 1];
        DFS(0);
    }
 
}

 

https://we1cometomeanings.tistory.com/266

[java 백준] 실버 2 / 1182번 부분수열의 합

[java 백준] 실버 2 / 1182번 부분수열의 합

재귀를 구현할때는 백트래킹이 끝날때까지 생각해보면 좋다. 1182번 문제같은 경우는 수열이 끝날때까지 재귀를 계속 돌려준다. 그렇기에 1182번의 백트래킹의 기준점은 수열이 끝날때이고, 수열이 끝날때 return이 된다.그렇기에 1182번 DFS메서드의 매개변수인 i와 15649번의 DFS메서드의 매개변수인 depth는 백트래킹이 끝날때까지의 깊이를 카운트해준다는 점에서 유사하다. 

 다시 이번문제인 15649로 돌아와보자. 예를 들어 1부터 4까지 있을 때 이걸 2개씩 출력하면 부분집합이 16개 생긴다.여기서 백트래킹의 기준은 2개씩 출력되는 것이고, 재귀는 깊이가 0일때부터 시작하여 2까지 될때까지 반복된다.

 

 

정말 재귀는 너무 어렵다... ㅜ 

 

 

참고 자료

 

https://st-lab.tistory.com/114

[백준] 15649번 : N과 M (1) - JAVA [자바]