[백준/Java/백트래킹] N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

예제 입력1

• 3 1

예제 출력 1

• 1
• 2
• 3

 

예제 입력 2 

• 4 2

예제 출력 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

 

예제 입력3

• 4 4

예제 출력3

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

 

Backtracking 방식

import java.util.*;

public class Main {
    static int n, m;
    static int[] result;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        result = new int[m];
        visited = new boolean[n + 1];

        backtrack(0);
    }

    static void backtrack(int depth) {
        if (depth == m) {
            for (int num : result) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            result[depth] = i;
            backtrack(depth + 1);
            visited[i] = false;
        }
    }
}

 

Brute Force 방식

import java.util.*;

public class Main {
    static int n, m;
    static int[] result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        result = new int[m];

        bruteForce(0);
    }

    static void bruteForce(int depth) {
        if (depth == m) {
            // 중복 체크
            Set<Integer> set = new HashSet<>();
            for (int num : result) {
                if (set.contains(num)) return; // 중복이면 출력 안 함
                set.add(num);
            }
            for (int num : result) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            result[depth] = i;
            bruteForce(depth + 1);
        }
    }
}

 

완전탐색 vs 백트래킹

 

방식	설명	예
완전탐색	조건에 상관없이 모든 경우의 수를 생성한 뒤, 유효한지 확인	모든 중복순열 생성 → 그중 유효한 순열만 출력
백트래킹	조건을 만족하지 않는 경우, 애초에 선택하지 않음 (탐색 전 가지치기)	숫자가 이미 사용됐다면 탐색 안 함

 

완전탐색

백트래킹

 

참고

DFS의 구현 방법은 2가지

구현 방식	설명	스택 사용 여부
재귀 함수	JVM 내부의 호출 스택(Call Stack) 을 사용	내부적으로 스택 사용
스택 자료구조	직접 Stack 자료구조 사용	명시적으로 스택 사용