jihun's study log

백트래킹

6 min read

백트래킹

정답 후보를 만들어가다가 조건을 위반하면 되돌아가는 알고리즘 기법

용어

  • 유망(promising) : 현재 상태(노드, 경로)가 문제의 해답으로 발전한 가능성이 높은지를 판단하는 기준
  • 가지치기(pruning) : 탐색 중 불필요한 경로를 제거하여 탐색의 효율성을 높이는 방법

백트래킹 구성요소

  • 선택(Decision)
    • 현재까지 만든 ‘부분 해’에 하나를 더 붙여서 다음 단계로 이동하는 행위
  • 조건(Constraint)
    • 선택한 결과가 규칙을 위반하거나 목표 달성이 불가능해 보이면, 더 이상 깊게 진행하지 않고 되돌아가는 판단 즉시 위반 조건 (해당 선택이 규칙, 조건을 위반함)
    • 불가능한 조건 (지금 위반은 아니지만 앞으로의 과정에서 해답을 만들 수 없음)
  • 종료(Goal)
    • 정답 조건을 만족하는 완성 상태에 도달했을 때 처리하는 부분
    • 정답을 찾으면 ‘카운트/저장’하고 돌아감
    • 정답을 찾으면 ‘즉시 종료’할 수도 있음
    • 정답을 카운팅 하는지, 저장하는지, 바로 종료하는지를 구분하여 처리

백트래킹 의사코드 예시

function solve(현재상태):
  [종료] 정답이 완성되었나?
    정답 처리(카운트/저장/출력/return)

  for 각 선택지 in 가능한 선택들:
    [조건]이 선택 가능한가?
      가능하면:
        선택 적용(체크/배열 갱신)
        solve(다음상태)
        선택 복구(원상복구)

백트래킹이 필요한 문제 특징

이 조건 만족 시 백트래킹을 고려해볼 필요가 있다.

  • 경우의 수가 많음
  • 하나씩 선택하면서 정답을 만들어간다
  • 중간에 조건 위반을 판단할 수 있다
  • 조건 위반이면 더 진행할 필요가 없다

백트래킹 문제 유형

순열 : N개의 숫자를 순서 있게 나열(중복 없음) -> 이미 사용한 숫자를 다시 사용하지 않음 조합 : N개 중 R개를 선택하고, 순서 상관 없음 -> 뽑고 남은 개수가 R개를 채울 수 없으면 중단 부분집합 : 각 원소를 선택/비 선택하는 모든 경우의 생성 -> 부분 집합의 합, 조건을 만족하는 집합이 없다면 중단

조건 만족 배치 문제

  • 공간(배열, 격자 등)에 배치
  • 서로 충돌하면 안됨
  • N-Queen
  • 스도쿠
  • 그래프 색칠 (인접 노드 같은 색 x) 문제

목표값 만들기 (합/식/카운트)

  • 숫자들을 이용한 형태
  • 합이 K개 되는
  • 목표값을 만들 수 있는지
  • 경우의 수 카운팅

문자열/숫자 생성 문제

  • 특정 조건을 만족하는 문자열 생성
  • 숫자 자릿수 구성
  • 비밀번호 생성 문제
  • 숫자 이어 붙이기 문제
  • 중복 없는 문자열 만들기 문제

경로/이동 문제

  • 시작 지점에서 도착까지 경로 찾기
  • 탈출할 수 있는지 확인하는 문제

N-Queen 문제

N x N 크기의 체스판 위에 N개의 Queen들을 서로 위협하지 않게 배치하는 문제

문제 링크 : N-Queen

  • 8x8 크기의 체스 판 위에 8개의 Queen들을 서로 위협하지 않게 배치하는 모든 경우의 수를 구하는 문제
  • 모든 경우의 수는
  • 실제 정답의 수는 92개
  • 모든 경우의 수 속에서 92개를 최대한 효율적으로 찾아내는 것이 관건
import java.util.*;
 
public class Main{
	static int answer = 0;
	static int N;
	static int[] visited;
	static int[][] arr;
 
  // 백트래킹
	static void BT(int depth) {
		if (depth==N) {
			answer++;
			return;
		}
		for (int i=0; i<N;i++) {
			if (search(depth,i)) {
				visited[depth] = i;
				BT(depth+1);
				visited[depth] = -1;
			}
		}
	}
 
  // 겹치는지 확인 (겹치면 false를 반환)
	static boolean search(int i, int j) {
		for (int y=0; y<i; y++) {
			if (visited[y]==j) return false;
 
			if (Math.abs(i-y) == Math.abs(j - visited[y])) return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
    // 할당
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		visited = new int[N];
		Arrays.fill(visited, -1);
    // 백트래킹
		BT(0);
		System.out.println(answer);
	}
}

그래프 뷰