백준 10974번 모든 순열 (java)

 

1. 문제

2. 코드

N이 주어졌을 때 구할 수 있는 모든 순열을 사전순으로 출력하는 문제이다. DFS 알고리즘을 순열을 구했다.

 

1. 필요한 배열 : 데이터를 담을 배열과 방문했는지 안했는지를 기록할 visited 배열 2개를 만든다.

2. 첫자리에 올 수를 반복문을 통해 하나씩 넣는다. 사전순이으로 출력해야하니까 1부터 쭉 넣어준다.

3. 배열에 넣은 수는 visited[] 배열을 통해 방문 했음을 표시한다. 그리고 방문한 곳을 제외하고 다시 반복문을 돌린다.

4. 모든곳을 방문하면 현재 값을 출력해주고 return으로 종료해준다.

 

depth는 현재가 몇번째 반복문을 돌고있는지를 표시해주고, start는 이번에 넣을 데이터이다. base case로 depth가 n과 같아지면 종료를 해준다.

import java.util.Scanner;

public class Main {

    public static void permutation(int arr[], boolean visited[], int n, int start, int depth){
        arr[depth] = start;

        if (depth == n) {
            for (int i = 1; i <= n; i++)
                System.out.print(arr[i] + " ");
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (visited[i] == true)
                continue;
            visited[i] = true;
            permutation(arr, visited, n, i, depth + 1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int arr[] = new int[n+1];
        boolean visited[] = new boolean[n+1];

        for(int i=1;i<=n;i++){
            visited[i] = true;
            permutation(arr, visited, n, i, 1);
            visited[i] = false;
        }
    }

}