[백준] 10974번 모든 순열 자바

문제 (실버3)

 

10974번: 모든 순열

 

 

 

문제 풀이

 

✔️ 사용 변수

문제에서 주어지는 순열 출력 숫자 : int N

출력 순서를 늘려나갈 숫자 변수: int depth

하나의 경우를 담아 출력할 배열 : int[] result

해당 숫자를 사용했는지 여부를 체크하기 위한 배열: boolean[] visited

 

✔️permutaion알고리즘

- 아래 그림처럼 각각의 시작 숫자로 사용하지 않은 숫자로 result배열을 채워나가면서 계속해서 재귀 호출한다.

- 한 번의 수행 후에(마지막 배열의 호출이 끝난 후) 다시 visited배열을 초기화해가면서 사전 순으로 수를 담는다.

 

 

 

소스 코드

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int[] result = new int[N+1];
		boolean[] visited = new boolean[N+1];
		permutation(N, 1, result, visited);
		sc.close();
	}
	
	public static void permutation(int n, int depth, int[] result, boolean[] visited) {
		if(depth == n+1) {
			for(int i = 1; i < n+1; i++)
				System.out.print(result[i]);
			System.out.println();
			return;
		}
		
		for(int i = 1; i < n+1; i++) {
			if(visited[i] == false) {
				result[depth] = i;
				visited[i] = true;
				permutation(n, depth+1, result, visited);
				visited[i] = false;
			}
		}	
	}

}