23.07.30

오늘은 백트래킹에 대해 알아보자.

 

백트래킹은 한국어로 퇴각검색이라고 하는데, 문제를 풀기위한 풀이를 이어나가다가 그 길이 답이 아닐 것 같으면 되돌아 가는 방식을 말한다. 이는 가지치기라고도 부르는데, 이 편이 이해하기 쉬울 듯 하다. 가지치기를 얼마나 잘하느냐가 효율성을 결정한다.

 

문제를 한 번 풀어보자.

 

https://www.acmicpc.net/problem/6603

6603번: 로또

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

 

이해를 위해 시간이 오래 걸렸으나 푸는데 성공하였다.

위 문제에서는 백트래킹 시점을 6번째 자리 이전에 마지막 숫자를 넣을 때로 하였다.

설명은 아래 예시와 함께 보자.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
  static StringBuilder sb = new StringBuilder();
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static int k;
  static int[] S;
  static int[] a = new int[6];
  static boolean[] b;
  public static void main(String[] args) throws Exception {
    while (true) {
      String[] s = br.readLine().split(" ");
      k = Integer.parseInt(s[0]);
      if (k == 0) {
        return;
      }
      S = new int[k];
      b = new boolean[k];

      for (int i = 1; i <= k; i++) {
        S[i-1] = Integer.parseInt(s[i]);
      }
      solution(0, 0);
      System.out.println(sb);
      sb.setLength(0);
    }
  }

  public static void solution(int index, int start) throws Exception { // 백트래킹이 시작하는 시점은 6번째 자리 이전에 마지막 숫자를 넣었을 때
    if (index == 6) { // index는 숫자를 넣은 위치이므로 6번째 자리에 숫자를 넣으면 출력
      for (int i = 0; i < 6; i++) {
        sb.append(a[i]).append(" ");
      }
      sb.append("\n");
      return;
    }
    for (int i = start; i < k; i++) { // start는 b[] 내에서 비교를 시작할 위치
      if (b[i]) continue;
      b[i] = true;
      a[index] = S[i];
      sb.append(index+1 + " ");
      sb.append(i+1);
      sb.append("\n");
      solution(index+1, i+1);
      b[i] = false;
    }
  }
}

위 코드를 실행해보면 더 쉽게 알 수 있다.

1 1
2 2
3 3
4 4
5 5
6 6
1 2 3 4 5 6 
6 7
1 2 3 4 5 7 
5 6
6 7
1 2 3 4 6 7 
5 7
4 5
5 6
6 7
1 2 3 5 6 7 
5 7
4 6
5 7
4 7
3 4
4 5
5 6
6 7
1 2 4 5 6 7 
...

첫 번째 숫자는 숫자를 넣을 위치, 두 번째 숫자는 몇 번째 숫자를 넣을지 알려주는 역할을 하도록 설정했다.

예시에서는 편의상 각 숫자의 순서와 번호를 동일하게 했다.

6번째에 6을 넣은뒤, 1 2 3 4 5 6을 출력하고, 6은 이미 사용했으므로 그 다음에는 6번째에 7을 넣는다.

이후 반복문이 종료돼 5번째 숫자를 입력할 때로 돌아가서, 이 때 5는 이미 사용했으므로 6을 입력하고, 6번째에 7을 입력한다.

또 반복문이 종료돼 5번째 숫자를 입력할 때로 다시 돌아가서, 이 때 5와 6은 이미 사용했으므로 7을 입력한다. 여기서 7을 입력하는 순간 반복문이 종료되고, 백트래킹, 즉 가지치기가 된다. 이 반복문이 종료되면 4번째 숫자를 입력할 때로 돌아가게 되고, 이를 반복한다.