[Baekjoon] 백준 10974번: 모든 순열 (JAVA)

문제 10974

10974번: 모든 순열

[ 문제 풀이 ]

N에 대한 모든 순열들을 출력해야 하는 문제로, DFS 탐색을 활용하여 모든 경우의 수를 탐색하면 됩니다. visit[]으로 이미 뽑은 숫자는 다시 뽑지 않도록 하고, for()을 사용하여 배열에  탐색한 숫자를 하나씩 넣어줍니다.

dfs(1)부터 시작하여 1부터 탐색을 시작합니다. depth를 매개변수로 하여 현재 dfs()을 몇 번째 돌고 있는지 확인합니다. visit[]을 활용하여, 뽑은 숫자가 아니라면 res[]에 현재 위치의 숫자를 넣어주고, 방문 표시를 합니다. depth를 하나 늘려 dfs()을 다시 돌고, 그렇게 해서 depth가 N+1이 될 때의 현재 res[]를 출력하고 리턴합니다.

모든 숫자를 돌고 나서 뽑았던 숫자를 false로 돌려놓은 후, 그 다음 i 번째에 대해 다시 코드를 실행하게됩니다.

[ 코드 ]

import java.io.*;

public class Main {
    private static int N;
    private static int[] arr, res;
    private static boolean[] visit;
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        visit = new boolean[N+1];
        res = new int[N+1];

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

        dfs(1);
    }

    private static void dfs(int depth) throws IOException {
        if (depth == N+1) {
            for (int i = 1; i <= N; i++) {
                bw.write(res[i] + " ");
            }
            bw.newLine();
            bw.flush();
            return;
        }

        for (int i = 1; i < N+1; i++) {
            if (visit[i]) continue;

            res[depth] = arr[i];
            visit[i] = true;
            dfs(depth+1);
            visit[i] = false;
        }
    }
}