백트래킹
[백준]
해당 문제는 백준에 존재하는 가장 기본적인 백트래킹인데요.
기본적으로 재귀를 사용하며 문제를 풀어가는데, 만일 재귀를 사용할 때 현재 노드가 조건에 위배가 된다면 현재 밟고 있는 노드를 제외하고 다음으로 넘어가는 방식입니다.
재귀를 쓰기 때문에 DFS와도 관련이 깊습니다. 그 외에도 백트래킹을 구현하는 방법은 있지만 이 문제는 DFS로 풀어볼게요. DFS는 제가 노션으로 따로 정리해둔 것이 있어서 추후에 붙여서 설명을 하겠습니다. 일단 이번 포스팅에서 중요한건 백트래킹이니 해당 알고리즘을 분석할거에요.
백트래킹의 정의
- 모든 경우의 수를 시도하면서 조건에 맞지 않으면 중간에 탐색을 중지하고 다음 경우로 넘어가는 방식.
문제 분석
- 문제에서
N개의 숫자 중 중복 없이M개의 숫자를 선택해야 합니다. - 예로,
N = 4,M = 2라면 1, 2, 3, 4 중에서 두 개의 숫자를 뽑아 가능한 모든 조합을 나열해야 하죠. - 숫자가 또한 중복되지 않아야 하기 때문에 방문처리를 통해 다시 선택할 수 없게 해야합니다.
백트래킹 적용 방식
- 재귀 호출을 통해 깊이(depth)까지 탐색을 하다가, 원하는 조건을 만족하면 저장하고, 그렇지 않으면 돌아갑니다.
depth는 현재 선택한 숫자의 개수를 의미하며depth가M이 됐을 때 결과를 출력하게 만들면 됩니다.- 각 자리(
depth가 1부터 N까지 숫자 중에서 하나를 선택하며, 방문처리를 통해 다시 선택할 수 없게visited배열을 사용해 관리합니다. depth가M에 도달하면, 현재 배열(arr)에 저장된 숫자들을 출력한 후 이전 단계로 되돌아가 다른 경우의 수를 탐색합니다.
private static void backtracking(int depth) {
if (depth == m) { // depth가 m이 되면, M개의 숫자를 다 선택했음을 의미
for(int val: arr){
sb.append(val).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < n; i++) { // 0부터 n-1까지 숫자 선택 시도
if(visited[i] == false) { // 방문하지 않은 숫자만 선택
visited[i] = true; // 현재 숫자를 선택
arr[depth] = i + 1; // arr 배열에 선택한 숫자 저장
backtracking(depth + 1); // 다음 깊이로 이동
visited[i] = false; // 현재 숫자를 선택 해제 (백트래킹)
}
}
}이 코드에서는 모든 경우의 수를 탐색했을 때,
if (depth == m)
선택한 숫자들을 출력하고 그 후, return을 통해 해당 재귀 함수를 불러들였던 시기 다음으로 갑니다.
visited[i] = false;
그 후 방금 자신이 마지막에 선택했던 숫자를 방문 해제를 하며, 다른 숫자를 선택합니다.
방문 해제(백트래킹)를 하지 않는다면?
바로 예시를 보면서 확인해보면 되겠죠.
백준에서 주어진 N = 4, M = 2를 넣어보겠습니다.
[1, 2], [1, 3], [1, 4]를 다 선택했으면 재귀를 불러들인 코드로 돌아가게 되겠죠.
이 때, 우리는 [2, X]으로 넘어가야 할텐데?
실상은 저 위에 있는 [1, 2], [1, 3], [1, 4]만이 답으로 도출될 것입니다.
왜?
내가 이미 방문을 했다고 생각하고 있기 때문에 더 이상 다음 단계로 넘어갈 수 없다.
우리가 선택했던 숫자를 돌아올 때마다 해제를 해줘야 하지만 그러지 않았기 때문에 1, 2, 3, 4 전부 visited[i] = true 상태가 되어있습니다. 우리는 false여야지만 숫자를 다시 선택할 수 있는데 그럴 수가 없는 것입니다.
그렇기 때문에 우리는 돌아와서 다시 가지치기를 하기 위해서는 반드시 백트래킹을 사용해야 합니다.
전체 코드
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int m;
static boolean[] visited;
static int[] arr;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
visited = new boolean[n];
arr = new int[m];
backtracking(0);
System.out.println(sb);
}
private static void backtracking(int depth) {
if (depth == m) {
for(int val: arr){
sb.append(val).append(" ");
}
sb.append("\n");
return;
}
for (int i = 0; i < n; i++) {
if(visited[i] == false) { // => if(!visited[i])와도 같은 코드.
visited[i] = true; // 현재 숫자를 선택
arr[depth] = i + 1; // 숫자 저장
backtracking(depth + 1); // 다음 재귀로 이동
visited[i] = false; // 현재 숫자를 선택 해제(백트래킹)
}
}
}
}
