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

Link: 백준

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

문제 설명

백트래킹 개념을 잡는데 아주 도움이 되는 기본문제입니다.
백트래킹을 사용하면 O(N^N) 시간 복잡도에 문제를 해결 할 수 있습니다. (중복 회피 경우 O(N!)

풀이

백트래킹은 기본적으로 재귀 호출을 사용합니다.
아래 코드 구조를 기반하여 문제를 해결 할 수 있습니다. (이부분은 외워주세요!)

backtracking(int[] nums, boolean[] visited, int depth){
   if (M == depth) {
       // 출력 저장 코드를 적어주세요.
       return;
   }


   for (int i = 1; i <= N; i++){
       // 중복을 제외해야하는 경우
       if (!visited[i]){
           visited[i] = true;
           backtracking(nums, visited, depth + 1);
           visited[i] = false;
       }
   }
}

솔루션 Github

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

public class Main {
   /*
   1. 아이디어
       - 백트래킹
   2. 시간복잡도
       - N! = 8! < 10 ^ 8 < 1s
   3. 자료구조 & 알고리즘
       - Backtracking
   */
   static int N, M;
   static int[] nums;
   static boolean[] visited;
   static StringBuilder output = new StringBuilder();


   public static void backtracking(int depth){
       if (M == depth) {
           for(int n : nums) {
               output.append(n).append(" ");
           }
           output.append("\n");
           return;
       }


       for (int i = 1; i <= N; i++){
           if (!visited[i]){
               nums[depth] = i;
               visited[i] = true;
               backtracking(depth + 1);
               visited[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());


       visited = new boolean[N + 1];
       nums = new int[M];


       backtracking(0);
       System.out.print(output);
   }
}