백준[자바]_15649_N과M_백트레킹

백트레킹이란 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드(나를 호출한 지점)로 돌아가 다른 자식 노드를 찾는 방법이다. 모든 경우의수를 찾아보지만, 그 중에서도 가능성이 있는 경우의 수만 찾는다. 재귀를 통해 구현한다.

브루트포스와 백트레킹, DFS를 혼동한 경우가 많아서 한 번 정리하고 가겠다. 

예를 들어 다음과 같은 문제가 있다고 가정하겠다. "a + b + c = 20을 만족하는 수를 모두 찾으시오.(0<=a,b,c<=10)"

 

브루트 포스 

모든 경우의 수를 모두 탐색한다. 즉, a,b,c =1부터 시작하여 a,b,c=10까지 총1000(10^3)개의 경우의 수를 모두 찾아보면서 조건에 맞는 값을 탐색하는 것이다. 모든 값을 탐색하다보니 조건에 맞는 값을 100% 모두 찾을 수 있다는 장점이 있지만, 그만큼 시간이 오래걸리고 많은 자원을 필요로 한다는 단점이 있다.

백트레킹

해당 범위 내에서 조건을 추가적으로 적용하여 특정 값이 조건을 만족할 만한지 유망성을 판단하는 것이다. a,b,c중 하나라도 11일 경우 조건을 만족하는 경우가 주어진 조건 안에서 절대로 존재할 수 없기 때문에 이 경우는 탐색하지 않는다. 이런식으로 탐색의 경우의수를 최적화하여 자원의 수를 축소할 수 있다. 

DFS

트리 순회의 한 형태이다. 하나의 순회 알고리즘으로 백트레킹에 사용하는 대표적인 탐색 알고리즘이다. 즉, 백트래킹 = DFS가 아니라 백트레킹을 구현하는 방법 중 하나가 DFS인 것이다. BFS로도 충분히 백트레킹을 구현할 수 있다.

 

연습 문제 풀이 

백준 15649 N과 M

문제

재귀를 사용하여 구현해보도록 하겠다. 

브루트 포스로 했다면 모든 경우의 수를 탐색해서 다음과 같이 출력 했을 것이다. 

1 1

1 2

1 3

...

3 1 

3 2 

3 3

하지만 문제의 조건을 보면 중복은 허용하지 않으며, 크기는 증가하는 순서로 출력하라고 했다. 

아래의 코드를 보고 그 진행과정을 파헤쳐보자.

package BackTracking;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _15649_N과M {
    static int n,m;
    static int arr[];
    static boolean check[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        //입력값 배열 초기화
        arr   = new int[m+1];//출력할 결과를 담을 배열
        check = new boolean[n+1];
        
        dfs(0); //시작 깊이 0
        
        
        System.out.println(sb);
        //depth변수를 추가하여 한 번의 dfs로 값을 조건에 맞는 답을 찾았으면
        //+1해서 탐색 깊이와 동시에 조합을 이루는 수의 개수를 같이 카운트 해준다. 
        //즉 4개의 수를 조합해야 할때 깊이가 1이면 1개의 숫자를 고른 것이고, 
        //깊이가 4이면 탐색이 끝난 것
        //탐색을 마치고 깊이를 +1해야 한다.
        
    }
    private static void dfs(int i) {
        // TODO Auto-generated method stub
        //재귀를 사용할 때는 base영역과 recursion영역을 명시해서 나누어 주어야 한다. 
        //이번 문제에서 베이스는 따로 주지 않고, 조합을 모두 구한 경우 출력을 하고 다시 호출한 지점으로 돌아가서 다른 수를 조합해볼 수 있도록 
        //재귀함수 내부에 반복문을 구현할 것이다 .
        
        
        //base
        if(i == m) {
            for(int k : arr) {
                if(k==0) continue;
                sb.append(k).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        //recursion 
        for(int k=1; k<=n; k++) {//인덱스와 값을 동일시 했기 때문에 1~n까지 반복을 수행한다. 
            if(!check[k]) {//아직 방문하지 않았다면
                check[k] = true;
                arr[i] = k;
                dfs(i+1);
                check[k] = false;
            }
        }
        
    }
 
}
 

 

필자 또한 재귀를 처음봤을 때, 이해가 잘 가지 않아서 엄청 고생했지만,, 그래서 예제 입력을 집적 보면서 실행과정을 보려한다. 

입력 예제가 4 2일 때의 경우의 수를 필자가 작성한 코드를 참고해서 살펴보자. 

1~4사이의 수 중에서 중복없이 2개를 뽑아 오름차순으로 나열해야 한다. 오름차순으로 나열하기 위해 정렬을 사용하는 것보다, 반복문을 사용해서 경우의 수가 1씩 증가하게 만드는 것이 더 직관적이다. 

depth 즉, 깊이 값으로 0을 주고 시작했다. 탐색을 1회 실행하고 하나의 숫자를 찾으면 깊이 + 1해서 다음 깊이, 즉 재귀를 호출한다. 이런식으로 하다보면 depth가 0일때, 1개의 수가 자리잡힌 것이고, 일반화하면 depth가 n-1일때, n개의 수가 조합을 이룬 것으로 볼 수 있다. 이런식으로 깊이 값을 체크해주면서 깊이 값이 m과 같아지면 출력을 하고 자신이 호출당한 지점으로 돌아가도록 했다. 

 

재귀의 처음부터 살펴보자. 

처음으로 호출했을 때, base의 조건이 성립하지 않으므로 바로 반복으로 들어간다.

k=1일때 부터 시작하는데, 가장 처음이므로 방문 배열 check의 모든 요소가 false인 상태이다. 다음에 다시 왔을때, 중복수를 출력하는 것을 방지하기 위해서 방문한 값은 true값을 줌으로써 방문 표시를 해주고 결과를 출력할 배열 arr에 현재 k값 1을 넣어주고, 재귀호출을 한다. 

깊이가 1일 때, base에 포함되지 않으므로 또 반복에 들어가는데, 새롭게 들어왔기 때문에 다시 k=1부터 시작한다. 

하지만 방금 전에 1은 이미방문해서 방문 표시를 했기때문에 1은 건너 뛰고 2를 방문해서 arr에 넣고. 재귀 호출을 한다. 

깊이가 2일 때, base에 포함되기 때문에 지금까지 arr에 저장했던 값을 sb에 저장하고 함수를 종료한다. 

그러면 자신을 호출했던 지점(depth=1, k=2인 지점)으로 돌아간다.

방문했던 지점에 대한 방문 표시를 지워주고, k=3가 되어 3을 방문해서 위와 같은 방식으로 1 3을 sb에 저장한 뒤 종료한다. 

호출한 지점(depth=1,k=3)으로 돌아가서 3에 대한 방문 표시를 지워주면 메소드가 return이 아니라 끝난 상태이다. 따라서 메소드가 종료되어 마지막으로 호출한 지점(depth=0, k=1)으로 돌아간다.

여기서 하나의 큰 틀이 수행되었다. 현재 상황은 작업을 수행하고 종료되어 호출 지점으로 돌아오면서 모든 방문 표시를 지워주었고, 첫 값이 1인 경우는 모두 sb에 저장했다. 

depth=0이고 반복첨자 k가 2로 증가하여 조합이 2부터 시작하게 된다. 

이런식으로 4까지 총 4번을 반복한다.

 

설명을 마치고 보니 읽어도 이해가 안될 것 같다라는 생각이 든다. 추후에 이미지를 첨부하여 이해에 도움을 주도록 하겠다. 

 

 

 

 

참조 : https://st-lab.tistory.com/114