[Baekjoon Online Judge] 10974번: 모든 순열

10974번: 모든 순열

요구사항

 - N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

 - 첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

 - 첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

---

DFS를 활용하여 풀이하였다. 순열을 사전순으로 출력해야 하기 때문에 입력이 3인 경우 첫 자리는 1, 2, 3이 올 수 있다. DFS를 활용하여 depth를 높여가며 output을 하나씩 방문해준다. 만약 depth의 깊이가 3과 같아지면 3개의 항목을 채웠다고 가정하고 즉시 출력해준다.

 

그 다음 방문기록을 false로 설정하고 다음 숫자를 깊이 있게 탐색을 진행한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Baekjoon10974 {

    static int[] output;
    static int n;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.valueOf(bufferedReader.readLine());
        int[] array = new int[n];
        output = new int[n];
        visited = new boolean[n];

        dfs(0);

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }

    private static void dfs(int depth) {
        if (depth == n) {
            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]) {
                visited[i] = true;
                output[depth] = i + 1;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}