[BOJ] 백준 10974 - 모든 순열 (자바)

순열,, 재귀...,,

순열(Permutation) 이란? 서로 다른 물건들 중 몇 가지 대상을 뽑아 일렬로 나열하는 것

나는 순열을 어떻게 짜는지 몰랐다. 재귀로 짜는건가? 백트래킹으로 짜는건가? 많은 생각을 했지만 짜지 못했고

다른 사람의 소스코드를 봤다.... 아주 간단하더라.

풀이

1. 존재하는 수만큼 visited[] 배열을 만들어준다. 똑같은 값이 2번 들어가지 않게

2. 첫자리에 올 수를 반복문을 통해 하나씩 넣는다.

3. 두 번째 자리 부터 반복문을 다시 돌리는데 이미 사용한 숫자는 사용할 수 없도록 visited[] 배열을 통해 제한한다.

4. 재귀의 깊이가 갖고 있던 수만큼 들어갔을 때 출력하고 return하여 현재 순열에서 빠져 나온다.

5. 끝;; 내가 설명을 많이 못한거같은데 코드를 보면 이해 갈 수 있을 것이다.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
public class Main {
    static int[] output;
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        output = new int[N];
        boolean[] visited = new boolean[N];
        for (int i = 0; i < N; i++) {
            visited[i] = true;
            DFS(arr, visited, N, i, 0);
            visited[i] = false;
        }
    }
 
    public static void DFS(int[] arr, boolean[] visited, int N, int start, int depth) {
        output[depth] = start + 1;
        if (depth == N - 1) {
            for (int i = 0; i < N; i++)
                System.out.print(output[i] + " ");
            System.out.println();
            return;
        }
        for (int i = 0; i < N; i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            DFS(arr, visited, N, i, depth + 1);
            visited[i] = false;
        }
    }
}