백준 10974번

모든 순열

문제

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

입력

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

출력

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

예제

알고리즘 분류

• 백트래킹
• 브루트포스 알고리즘

코드

import java.io.*;

public class Main {
	public static int N;
	public static int arr[];
	public static boolean visited[];	
	public static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		visited = new boolean[N];
		
		Func(0);
		System.out.println(sb.toString());
	}
	
	public static void Func(int depth) {
		if(depth == N) {
			for(int i=0; i<N; i++)
				sb.append(arr[i] + " ");
			
			sb.append("\n");
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(visited[i])
				continue;
			
			arr[depth] = i + 1;
			visited[i] = true;
			Func(depth + 1);
			visited[i] = false;
		}
	}
}

풀이

백트래킹 문제이다. DFS (깊이 우선 탐색)을 활용하여 문제를 해결한다.
중복이 불가능하기 때문에 boolean 타입의 visited 배열을 활용한다.