이건 공부해도 모르겠더라
백트래킹 알고리즘이 모든 경우의 수 brute force와 비슷해서 이해를 못하는 듯 하다.
백D브 차이백트래킹은 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법으로, 반드시 DFS만으로 가능하지 않고 BFS등으로도 가능한 기법이다.하나의 문제 해결 방법론이고 이러한 백트레킹을 구현하는 방법론 중 하나가 DFS이다.브루트 포스는 모든 경우의 수를 탐색하는 문제 해결 방법론이다.import java.io.*;
public class Main {
static int n;
static int[] map;
static int count=0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
for(int i=1; i<n+1; i++) {
map = new int[n+1];
map[1] = i; // (1,i)에 queen
dfs(2);
}
System.out.println(count);
}
static void dfs(int depth) {
if(depth > n) {
count++;
}
else {
for(int i=1; i<n+1; i++) {
map[depth] = i; // (depth,i)에 queen
if(check(depth)) {
dfs(depth+1);
}
// 없어도 됨. 이미 map[depth] = i에서 부모 퀸의 위치가 초기화 되었기 때문이다.
// map[depth] = 0;
}
}
}
static boolean check(int depth) {
for(int i=1; i<depth; i++) {
// 열이 같으면 false
if(map[i] == map[depth]) return false;
// 00 01 02 03
// 10 11 12 13
// 20 21 22 23
// 30 31 32 33
// (/\) 양방향 대각선
if(Math.abs(i-depth) == Math.abs(map[i]-map[depth])) return false;
}
return true;
}
}
모르겠다. 🤔🤔🤔
조금더 대표적인 문제를 살펴보자
LeetCode에 존재하는 백트래킹문제이다.
숫자를 입력하여 조합할 수 있는 모든 경우의 문장을 확인하는 문제이다. 많은 풀이 방법이 있지만 재귀를 사용한 DFS 풀이방식을 많이 사용한다.
class Solution {
HashMap<Integer,String> map;
private void solve(int i,String s,String digits,List<String> list){
if(i==digits.length()){
list.add(s);
return;
}
int digit=(digits.charAt(i))-'0';
String values=map.get(digit);
for(int j=0;j<values.length();j++){
solve(i+1,s+values.charAt(j),digits,list);
}
}
public List<String> letterCombinations(String digits) {
if(digits.length()==0) return new ArrayList<String>();
map=new HashMap<>();
map.put(2,"abc");
map.put(3,"def");
map.put(4,"ghi");
map.put(5,"jkl");
map.put(6,"mno");
map.put(7,"pqrs");
map.put(8,"tuv");
map.put(9,"wxyz");
List<String> list=new ArrayList<>();
solve(0,"",digits,list);
return list;
}
}