Baekjoon (백준) 10973 번

💻 Beakjoon 10974 번 문제 -Java

• Baekjoon 10974 번

문제 설명

문제의 설명은 간단하다.

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

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

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

(즉, 모든 경우의 순열을 출력하면 된다.)

접근 방법

그냥 순열로 풀수 있었지만, 많은 사람들이 그렇게 풀꺼 같아서 나는 백트레킹 알고리즘으로 코드를 구현하였다.

문제 풀이

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

public class Baek_j_10974 {
    static int N;
    static boolean vi[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        vi = new boolean[N];
        int arr[] = new int[N];

        dt(0,arr);
    }
    public static void dt(int dep,int arr[]){
        if(dep == N){
            for(int var : arr){
                System.out.print(var + " ");
            }
            System.out.println();
            return;
        }

        for(int i = 0; i < N; i++){
            if(!vi[i]){
                vi[i] = true;
                arr[dep] = i +1;
                dt(dep+1,arr);
                vi[i] = false;
            }
        }
    }
}

💡 문제 해결 과정 느낌점

• 점점 순열과 백트레킹 알고리즘에 익숙해지고 있다. 이 맛에 코딩한다..!