[알고리즘] 백트래킹

탐색 알고리즘

경우의 수(그래프의 노드)를 탐색하는 탐색 알고리즘, 그 중에서도 모든 경우의 수를 탐색하는 완전 탐색 알고리즘에는 크게 두 종류가 있는데, BFS(Breadth First Search - 너비 우선 탐색), DFS(Depth First Search - 깊이 우선 탐색)가 이에 속한다.

 

BFS는 큐를 이용해 현재 노드와 가까운 순서대로 노드를 탐색해 나가는 방법이고, DFS는 스택을 이용해 현재 노드와 연결된 다음 노드를 차례로 탐색해 나가는 방법이다.

 

참고로 함수 호출에 스택을 이용하기에 주로 재귀 함수를 이용해 DFS를 구현한다고 한다.

 

그래프 탐색 알고리즘에 대한 자세한 정보는 아래 링크를 참고하면 될 것 같다.

---

https://jin1ib.tistory.com/entry/BFS-DFS-1

그래프 탐색 알고리즘(Graph Search Algorithm)

 

 

---

 

 

백트래킹

백트래킹 또한 탐색 알고리즘의 일종으로써, 재귀 호출을 통해 구현 가능하다.

 

재귀 호출을 이용한다는 점에서 백트래킹은 DFS와 공통 분모가 있어 보이지만 차이점이 존재한다.

 

DFS는 모든 경우를 탐색해 나가지만, 백트래킹은 탐색 중에 현재 단계(노드)에서 특정 조건을 확인한 뒤 이를 만족하는 경우에만 다음 재귀를 진행한다.

 

여기서 특정 조건을 확인하여 재귀 여부를 결정하는 것을 가지치기(pruning)이라고 한다.

 

백트래킹에서는 가지치기를 위해 유망 함수(promising function)라는 것을 만들어 판단한다.

 

이전 포스팅에서 해결했던 문제(N-Queen)에서 현재 놓으려는 퀸의 위치가 유효한지 판단하기 위해 사용했던 check() 메소드가 유망 함수라고 볼 수 있다.

 

 

---

 

 

백트래킹 문제 풀어보기

문제 링크: https://www.acmicpc.net/problem/15649

 

자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 프로그램을 작성하는 것이 목표이다.

 

일반적인 탐색이라면 첫 번째 숫자를 선택하면 그 다음에 숫자를 선택하는 데 제약이 없지만, 문제 조건에 의해 우리는 제약을 만들어야 한다.

 

어느 숫자를 선택했는지를 기록하기 위해 길이 n의 boolean 타입 배열 check를 사용해보자.

 

처음에 숫자를 고른 뒤 check에 이를 반영해주면, 다음에 숫자를 고를 때 check를 확인해보고 이미 사용된 숫자라면 해당 경우를 넘어갈 수 있을 것이다.

 

아래는 이를 반영한 문제 해결 코드이다.

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static StringBuilder sb;
    static List<Integer> perm;
    static boolean[] check;
    
    static void permutation() {
        if(perm.size() == m) {
            for(int e : perm) {
                sb.append(e).append(" ");
            }
            sb.append("\n");
            return;
        }

        for(int i = 0; i < n; i++) {
            if(check[i] == false) {
                check[i] = true;
                perm.add(i + 1);
                permutation(depth + 1);
                perm.remove(perm.size() - 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];
        perm = new ArrayList<Integer>();
        sb = new StringBuilder();

        permutation();
        System.out.print(sb);
    }
}

 

코드를 보면 permutation()의 if문 내에서 check를 통해 이미 선택한 숫자인지 확인하는 수식이 유망 함수라고 볼 수 있다.

 

check[i]가 false면 아직 선택하지 않은 숫자이므로 수열을 담은 perm 리스트에 숫자를 추가한 뒤 다음 재귀로 넘어가 perm의 크기가 m이 될 때까지 반복한다.

 

크기가 m이 되었다면 perm에 중복 없이 숫자를 m개 담았다는 의미이므로 안에 담긴 숫자들을 차례로 출력하면 된다.

(빠른 출력을 위해 StringBuilder를 사용)

 

재귀가 끝나면 check, perm을 원상 복구한 뒤 다른 숫자로 위 과정을 반복하며 계속 순열을 만들어낸다.

---

재귀 종료 후 원상 복구 작업이 필요한 이유

한 경우(노드)에서 조건을 만족해 재귀를 진행한 경우, 재귀가 종료되면 재귀 이전에 진행한 작업을 원상 복구해야 다음 경우(형제 노드)에서 방해받지 않고 탐색을 진행할 수 있다.

 

for문 내에서 다음 숫자를 선택하는 재귀를 위해 check[i]를 true로 바꾼 뒤, 재귀가 종료되면 다시 false로 바꾸어야만 다음 탐색이 방해받지 않고 진행될 수 있다.

false로 바꾸지 않는다면 이전 탐색이 끝났는데도 결과가 남아 올바른 다음 탐색을 진행할 수 없다.

 

check[i] = false 이 부분만 주석처리 하여 실행한 뒤 입력으로 n = 5, m = 3을 전달해보자.

실행 과정 중 1, 2를 고른 상황에서 재귀 호출을 통해 마지막 숫자를 3으로 골라 출력했다면 재귀가 끝나 다시 돌아올 때 3 자리가 false로 바뀌지 않는다.

 

이는 마지막에 4와 5를 출력할때도 마찬가지이므로 최종적인 출력 결과는

1 2 3
1 2 4
1 2 5

가 되어 문제를 해결할 수 없다.

왜냐하면 두 번째 숫자를 출력하는 경우에서 2를 선택한 경우가 모두 끝났지만 재귀 안에서 선택된 3, 4, 5가 다음 두 번째 숫자를 선택하는 데 영향을 끼치기 때문이다.

 

그 결과 check 배열의 모든 요소가 true가 되어 이후의 1 3 2, 1 3 4와 같은 순열을 선택해 출력할 수 없다.

따라서 현재 경우에서 조건을 만족해 호출하는 재귀가 종료되었다면 다시 원상태로 복구하는 작업이 필요하다.