[백준 | 10974] 모든 순열- Java

문제

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

입력

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

출력

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

예제 입력

입력	출력
3	1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

내 제출

import java.util.Scanner;

public class Main {

    static int[] arr;
    static boolean[] visited;
    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];
        visited = new boolean[N];
        dfs(0);
    }

    public static void dfs(int depth) {
        if (depth == N) {
            for (int i : arr) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i + 1;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}

풀이과정

백트래킹 알고리즘을 사용하여 문제를 해결하였습니다. 

 

• 기저 조건 생성
  • `depth`가 `N`과 같을 때, 즉 배열의 모든 위치가 채워졌을 때 현재 순열을 출력합니다.
  • 출력 후에는 호출했던 곳으로 돌아가 다른 가능한 순열을 탐색합니다.
• 방문 배열 사용
  • `visited` 배열을 사용하여 각 인덱스가 현재 순열에 포함되어 있는지 확인하였습니다.
  • visited[i]가 true인 경우, 인덱스 i는 현재 순열에 포함되므로 다음 탐색에서 제외합니다.
  • visited[i]가 false인 경우, 인덱스 i를 현재 순열에 포함시키고 다음 단계로 진행합니다.
  • 재귀 호출 후에는 visited[i]를 false로 돌려놓아 다른 순열 생성 시 이 인덱스를 사용할 수 있도록 하였습니다.
• 재귀 호출과 백트래킹
  • 순열의 현재 깊이에서 가능한 모든 인덱스를 탐색합니다. 각 인덱스를 포함시키고 다음 깊이로 진행합니다.
  • 재귀 호출 후에는 visited[i]를 false로 되돌려놓아 다른 순열 생성을 위해 인덱스를 다시 사용할 수 있도록 합니다.