백준 10974번 모든 순열 (java)

[Silver III] 모든 순열 - 10974

문제 링크

성능 요약

메모리: 81456 KB, 시간: 2172 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2025년 1월 9일 17:47:48

문제 설명

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

입력

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

출력

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

풀이

dfs로 완탐하면 끝이다.

전체 코드

public class Main {
    static int N;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N+1];
        dfs(0, new int[N]);
    }

    public static void dfs(int depth, int[] x){
        if(depth == N){
            for(int i = 0 ; i < N ; i++){
                System.out.print(x[i] + " ");
            }
            System.out.println();
            return;
        }
        for(int i = 1; i <= N; i++){
            if(!visited[i]) {
                visited[i] = true;
                x[depth] = i;
                dfs(depth + 1, x);
                visited[i] = false;
            }
        }
    }

}