[Algorithm] 백준 10974 모든 순열

[ 문제 ]

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 N;
	
	public static void permutation (int cnt, boolean[] isSelected, int[] output) {
		if (cnt == N) {
			for (int i = 0; i < N; i++)	System.out.print(output[i] + " ");
			System.out.println();
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (isSelected[i])	continue;
			
			output[cnt] = i + 1;
			isSelected[i] = true;
			permutation(cnt + 1, isSelected, output);
			isSelected[i] = false;
		}
	}
    
    
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		
		boolean[] isSelected = new boolean[N];
		int[] output = new int[N];
		permutation(0, isSelected, output);
		
		scanner.close();
	}
}