백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법.
최적화 문제와 결정 문제를 푸는 방법이다.
특징
- 해를 찾아가는 도중, 지금의 경로가 invalid 하다면 그 경로를 더이상 가지 않고 되돌아감. -> 즉 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것
가지치기를 얼마나 잘하느냐에 따라 프로그램의 효율이 달라짐
- DFS보다 효율적이다.
예시 1: BOJ 15649번: N과 M(1)
https://www.acmicpc.net/problem/15649
import java.util.Scanner;
class Main
{
static StringBuilder sb = new StringBuilder();
static int arr[]; // 출력값들이 저장된 arr배열
static boolean visit[]; // 방문한 곳을 저장하는 배열
static int n,m;
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
arr = new int[m];
visit = new boolean[n+1];
solution(0);
System.out.println(sb.toString());
}
// depth는 현재 보고 있는 arr배열의 인덱스를 뜻함
private static void solution(int depth) {
// depth가 m이라면 배열의 끝이므로 sb에 저장 후 return
if(depth == m){
for(int num : arr){
sb.append(num + " ");
}
sb.append("\n");
return;
}
// 1부터 N까지 방문하지 않은 곳을 확인
for(int i = 1; i <= n; i++){
if(visit[i]){
continue;
}
// 방문하지 않았다면 true 처리 후 depth에 i값을 넣어줌.
// 그 후 depth + 1로 recursion
visit[i] = true;
arr[depth] = i;
solution(depth+1);
// 다시 false 처리
visit[i] = false;
}
}
}
예시 2: BOJ 15650번: N과 M(2)
https://www.acmicpc.net/problem/15650
import java.util.Scanner;
class Main
{
static StringBuilder sb = new StringBuilder();
static int arr[]; // 출력값들이 저장된 arr배열
static int n,m;
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 방문한 숫자를 저장한 arr 배열
arr = new int[m];
solution(1,0);
System.out.println(sb.toString());
}
// pos : 시작하는 숫자(1~N) depth: arr의 인덱스(0~m)
private static void solution(int pos,int depth) {
// depth가 M이면 arr에 저장된 값들을 sb에 저장 후 return
if(depth == m){
for(int num : arr){
sb.append(num + " ");
}
sb.append("\n");
return;
}
// pos 값부터 n까지 방문
for(int i = pos; i <= n; i++){
arr[depth] = i; // i값 저장
solution(i+1, depth+1);
// solution에 호출 할 때 i + 1이어야 함.
// 방문한 값보다 커야하므로.
}
}
}
'CS > 알고리즘' 카테고리의 다른 글
Dijkstra algorithm (0) | 2024.01.11 |
---|---|
Priority Queue (1) | 2023.10.23 |
Stack & Queue 알고리즘 공부 (1) | 2023.10.14 |