DFS란?
- 깊이를 우선시 하여 탐색하면서 다음 브랜치를 탐색하는 방식
- 보통 재귀 호출 사용을 하는 순환 알고리즘 (+스택 구현도 있다)
- 모든 노드를 방문하는 탐색 방식
Backtracking이란?
- 유망한 가능성이 있는 노드들만 탐색하는 방식
(불필요한 경우의 수는 탐색 X) - 조건문 등의 방식으로 해가 되지 않는다면 탐색을 하지 않고 돌아가기 때문에 효율적
백준 백트래킹 예제
15649번 - N과 M 1
package Backtracking;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class NandM { //15649
/*
백트래킹은 가능성이 있는 경우의 수만 찾아보는 방법이다
백트래킹 종류인 깊이우선방식 DFS로 문제풀이
boolean[n] visit : 방문한 노드인지 check (해당 숫자 썼으면 T)
int[m] arr
*/
static boolean[] visit;
static int[] arr;
static StringBuilder sb= new StringBuilder();
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 m = Integer.parseInt(st.nextToken()); //길이
visit = new boolean[n];
arr = new int[m];
dfs(0,n,m);
System.out.println(sb);
}
public static void dfs(int depth, int n , int m){
if(depth == m){
for (int val : arr){
sb.append(val+ " ");
}
sb.append("\n");
return;
}
for( int i=0; i<n;i++){
if(!visit[i]){ //해당 숫자 사용하지 않았다면 arr에 저장
visit[i] = true;
arr[depth] = i+1;
dfs(depth+1, n, m);
visit[i]=false; //자식노드 방문 끝나고 돌아오면 방문 노드를 방문하지 않은 상태로 변경
System.out.println("visit"+i+":" + visit[i]);
}
}
}
}
input이 3 2 라 가정하고 그림을 그려보면,
될 수 있는 경우의 수는 6가지이다.
두 자리 중 쓴 값을 visit 로 묶어둔 뒤,
depth 값이 길이인 2가 되었을 때 if문으로 들어가 출력을 해줄 수 있게끔 한다.
재귀호출을 끝낸 후 visit배열의 값을 출력해보았다.
input: 3 2 일 경우의 출력 결과물.
15650번 - N과 M 2
package Backtracking;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class NandM2 {//15650
static int n; static int m;
static int[] arr;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();
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()); //길이
visited = new boolean[n+1];
arr = new int[m];
dfs(0, 1);
System.out.println(sb);
}
private static void dfs(int depth, int cur) {
if (depth == m) {
for (int i : arr) {
sb.append(i + " ");
}
sb.append("\n");
return;
}
for (int i = cur; i <= n; i++) {
if (!visited[i]) {
visited[i] = true;
arr[depth] = i;
dfs(depth + 1, i+1);
visited[i] = false;
}
}
}
}
dfs함수에 매개변수를 하나 더 두어서 오름차순이 가능하도록 하였다.
재귀는 역시 대입하면서 써가면서 풀어야 이해가 잘 된다.
15652번 - N과 M 4
package Backtracking;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class NandM4 { //15652
/*
N개의 수 중 M개를 중복가능하게 고른 수열
수열조건: 부등호를 포함하는 오름차순
*/
static int[] arr;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();
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 m = Integer.parseInt(st.nextToken()); //길이
visited = new boolean[n + 1];
arr = new int[m];
dfs(n, m, 0,1);
System.out.println(sb);
}
private static void dfs(int n, int m, int depth, int cur) {
if(depth == m){
for( int i :arr){
sb.append(i+" ");
}
sb.append("\n");
return;
}
for(int i=cur; i<=n;i++){
arr[depth] = i;
dfs(n,m,depth+1,i);
//i+1 대신 i 를 보내야 중복
}
}
}
dfs함수의 매개변수 n,m은 귀찮아서 생략하고 대입하였다..
처음 1번문제는 접했을 때는 감도 못 잡았는데 형식을 알고나니,
3,4 번은 어느 곳을 교체해야하는지 감이 와서 풀 수 있었다!
재귀와 return문을 잘 활용할 수 있도록 까먹지 말자~😊
𝐃𝐨𝐧'𝐭 𝐛𝐞 𝐚 𝐩𝐫𝐨𝐜𝐫𝐚𝐬𝐭𝐢𝐧𝐚𝐭𝐨𝐫💫