https://www.acmicpc.net/problem/15649
풀이
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 순열을 구하는 문제다.
check 배열을 사용해 중복 없이 M개를 고르고, 숫자를 pm 배열에 저장한다.
코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int n, m;
static boolean[] check;
static int[] pm;
static StringBuilder sb = new StringBuilder();
static public void permutation(int L) {
if (L == m) {
for (int i : pm)
sb.append(i + " ");
sb.append("\n");
}
else {
for (int i = 1; i <= n; i++) {
if (!check[i]) {
check[i] = true;
pm[L] = i;
permutation(L+1);
check[i] = false;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
check = new boolean[n+1];
pm = new int[m];
permutation(0);
System.out.println(sb);
}
}StringBuilder를 사용하면 메모리와 시간을 줄일 수 있다.
- 위에 풀이가
StringBuilder를 사용한 풀이, 아래의 풀이가System.out.println을 사용한 풀이
참고: JAVA 순열, 중복 순열, 조합, 중복 조합 구현
[백준] 15649번 : N과 M (1) - JAVA [자바]
재귀를 사용하여 백트래킹을 할 수 있다.
💡 백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지(유망하지 않은지) 판단하고 그러한 경우 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다.
여기서 알아둘 것은 특정 상태(노드)를 제외한다는 것이다.
백트래킹은 현재 상태(노드)에서 다음 상태(노드)로 나아갈 수 있는 모든 경우를 찾되, 그 중 유망하지 않다면 현재에서 더 이상 나아가지 않고 이전의 상태(노드)로 돌아가 다음 상태(노드)를 검사한다.
여기서 더 이상 탐색할 필요가 없는(유망하지 않은) 상태(노드)를 제외하는 것을 가지치기(pruning)라고도 한다.
즉, 이 방법을 통해 우리는 모든 경우의 수를 체크 하지 않고 필요한 것만 체크하여 전체 풀이 시간을 단축할 수 있게 된다!
백트래킹을 사용하는 알고리즘 중 하나는 대표적으로 DFS가 있다.
참고: 알고리즘 - 그래프 탐색(깊이 우선 탐색 - DFS)
DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색을 수행한 뒤 다시 돌아와 그 중 가장 최적의 경로를 반환한다.
백트래킹을 사용해 해결할 수 있는 문제는 의사 결정, 최적화, 열거하기 등의 경우가 있다.
사실 백트래킹은 사용 가능한 경우가 많지만 시간복잡도가 보통 Exponential(지수, 2^n 꼴)이며, 대부분 Dynamic Programming, 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다.
하지만 일부 경우의 문제들은 여전히 백트래킹으로만 해결이 가능한 문제도 있으며 그러한 경우에 많이 사용된다.
ex) N-Queen 문제
💡 참고) DFS와 백트래킹(Backtracking)의 차이
백트래킹의 방법 중 하나가 DFS인 것이다.
DFS는 기본적으로 그래프 형태 자료구조에서 모든 정점을 탐색할 수 있는 알고리즘 중 하나이다. 깊이를 우선적으로 탐색하기에 재귀 또는 스택을 이용한다.
재귀를 이용하여 탐색을 수행한다는 부분에서 완전탐색 알고리즘의 재귀 / 백트래킹(Backtracking)과 유사한 측면이 보여 혼란이 올 수 있다.
그런데, 재귀라는 것은 말 그대로 스스로의 함수(또는 메소드)를 호출하는 방식을 의미하는 것이므로 DFS가 재귀라는 방식을 이용해 탐색을 수행하는 것으로 하나의 방식이라고 이해하면 된다.
또한 백트래킹(Backtracking)은 재귀를 통해 알고리즘을 풀어 가는 기법 중 하나로 가지치기(Pruning)을 통해서 탐색을 시도하다가 유망하지 않으면 추가 탐색을 하지 않고 다른 해를 찾는 방법이다.
DFS는 기본적으로 모든 노드를 탐색하는 것이 목적이지만 상황에 따라서 백트래킹 기법을 혼용하여 불필요한 탐색을 그만두는 것이 가능하다.
즉, DFS와 백트래킹은 유사한 부분이 있으며 기본적으로 사용 목적이 다르지만 두 기법을 혼용하여 사용하는 것이 가능하다. 완전히 다른 개념이 아니라 재귀 호출을 통한 기법 중 하나 이기 때문이다.
