[백준/JAVA] BOJ 10974 - 모든 순열

👀 문제

10974번: 모든 순열 ✨ 실버 3

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

예제 입력

3

예제 출력

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

🔑 키포인트

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

✍️ 코드

package jan_week4;

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

public class BOJ10974 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());

		int[] per = new int[n];
		boolean[] used = new boolean[n];

		back(per, used, n, 0);
	}

	// 백트래킹
	public static void back(int[] per, boolean[] used, int n, int depth) {
		// depth가 n이면 출력 후 return
		if (depth == n) {
			for (int p : per) {
				System.out.print(p + " ");
			}
			System.out.println();
			return;
		}

		// 1부터 n까지 반복
		for (int i = 1; i <= n; i++) {
			// 사용하지 않은 숫자면
			if (!used[i - 1]) {
				per[depth] = i; // 값 넣어주기
				used[i - 1] = true;
				back(per, used, n, depth + 1); // 재귀
				used[i - 1] = false;
			}
		}
	}
}