21.08.31 기록

백준 알고리즘 15649 풀이

🎆해설(메모리 22.9MB, 시간 316ms로 통과)

-손코딩을 하다가 막혀서 그냥 해설을 봤는데, 재귀가 등장했다😂

• 백트래킹(backtracking)
  

  결과를 얻을 때까지 모든 가능성을 시도하는 것이다.
  

  모든 가능성은 하나의 트리처럼 구성할 수 있으며, 트리를 검사하기 위해 깊이 우선 탐색을 사용한다.
  

  보통 재귀 함수로 구현된다
  

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

public class B15649 {

    public static int N;
    public static int M;
    public static int[] nums;
    public static boolean[] visit;
    public 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());

        nums = new int[M];
        visit = new boolean[N];
        dfs(0);
        System.out.println(sb);
    }

    public static void dfs(int depth) {
        if(depth == M) {
            for(int i = 0; i < nums.length; i++) {
                sb.append(nums[i]).append(" ");;
            }
            sb.append("\n");
            return;
        }

        for(int i = 0; i < N; i++) {
            if(!visit[i]) {
                visit[i] = true;
                nums[depth] = (i+1);
                dfs(depth+1);
                visit[i] = false;
            }
        }
    }
}