Baekjoon 10974 모든 순열 JAVA

10974번: 모든 순열

문제

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

입력

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

출력

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

풀이

방문리스트를 이용하여 순차적으로 순열들을 생성하여 준다.

완전탐색의 한종류로 체크리스트와 재귀함수를 이용하여, 모든 나올 수 있는 수열들은 검색한다.

코드

import java.util.Scanner;

public class Main {
	static boolean c[] = new boolean[10];
	static int n, m;
	static char [] r= new char[10];
	public static void f(int m) {
		if(m==n) {
			for(int i=0;i<n;i++)
				System.out.print(r[i]+" ");
			System.out.println();
		}
		for(int i=1;i<=n;i++) {
			if(!c[i])
			{
				c[i]=!c[i];
				r[m]=(char)(i+'0');
				f(m+1);				
				c[i]=!c[i];
			}
		}		
	}	
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt();
		f(0);
	}
}