[백준 | Java] 10974 모든 수열

내 풀이

이 문제와 비슷한 '이전 수열', '다음 수열' 알고리즘으로 풀었을 때 테스트케이스 4까진 정답이었는데, 5부턴 틀린 답이 반환되었다.

따라서 swap을 이용한 순열 대신 visited로 순열의 방문을 체크하면 DFS 알고리즘을 사용하였다.

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

public class Main {
    static int[] res, arr;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        visited = new boolean[N];
        res = new int[N];  // 만들어진 순열 담을 배열

        for (int i = 0; i < N; i++) {
            arr[i] = i+1;
        }

        permutation(0);
    }

    static void permutation(int depth) {
        StringBuilder sb = new StringBuilder();

        if (depth == arr.length) {
            for (int i : res) {
                sb.append(i).append(" ");
            }
            System.out.println(sb);
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (visited[i])
                continue;
            else {
                visited[i] = true;
                res[depth] = i + 1;
                permutation(depth+1);
                visited[i] = false;
            }
        }
    }
}