[알고리즘] 되추적(Backtracking) 알고리즘

되추적(Backtracking) 알고리즘

 

되추적 알고리즘은 핵심은 '배제'와 '풀이 시간 단축'이다. 조건을 만족하는 모든 경우의 한에서 모든 조합을 탐색한다.

되추적 알고리즘은 적용할 수 있는 대표적인 완전 탐색 알고리즘은 깊이우선탐색(DFS)이다. 

 

 

깊이 우선 탐색(DFS)는 현재 노드에서 방문해야하는 곳까지 재귀나 스택을 이용해 단말 노드에 도착할 때

까지 깊이 곳을 탐색하는 방법이다. 하지만 DFS의 경우 모든 노드를 방문하기 때문에 굳이 방문해도 되지 않을 노드까지

방문하게되고 이로인해 비효율을 초래한다.

 

 

되추적 알고리즘은 이러한 비효율을 해결한다. 노드를 방문함에서 있어서 문제 해결에 가능성이 있지 않은 노드는 배제하므로써

비효율을 해결한다. 즉, 되추적 알고리즘은 DFS에 Pruning을 통해 가능성이 없는 노드를 배제하고 탐색하는 완전 탐색 방법이다.

 

되추적 알고리즘은 

 

1. 깊이 우선 탐색 시작

2. 각 노드가 유망한지 검사

3. 유망하다면 탐색을 계속해서 진행

4. 유망하지 않다면 부모 노드로 돌아가서 탐색을 계속 진행(백 트레킹)

 

의 순서로 진행된다.

 

되추적(Backtracking ) 과정 - N-Queen

dfs와 되추적 알고리즘을 이용해 해결할 수 있는 대표적인 문제는 n-queen 문제가 있다.

n-queen 문제란 n x n 크기의 체스판에서 가로 세로 대각선으로 움직일 수 있는 n개의 queen을 체스판에 올려둘 때,

n개의 queen이 서로 다른 queen을 공격할 수 없는 경우의 수를 구하는 문제이다.

 

위의 그림은 n = 8일 때 가능한 경우 중 하나이다.

원래 dfs에서 모든 경우를 탐색했다면 위의 그림은 다르게 나타났을 것이다. 모든 경우를 전부 탐색했을 것이고, n이 커질수록 탐색해야하는 양은 엄청나게 증가할 것이다. 백트레킹을 이용해 유망한 노드를 검사하고 만약 유망하지 않다면 더이상 깊이 탐색을 진행하지 않고 부모 노드로 백트레킹하게 된다.

 

너비 우선 탐색 구현

package algorithm;

import java.util.*;

public class nQueens {
	static int cnt, n;
	static int[] col;
	
	public static boolean isPossible(int c) {
		// 이전까지 입력된 열 중에 같은 행이 존재하는 지 확인
		for(int i = 1; i < c; i ++) {
			if(col[i] == col[c])
				return false;
			if(Math.abs(col[i] - col[c]) == Math.abs(i - c))
				return false;
		}
		return true;
	}
	
	public static void dfs(int row) {
		if(row == n) {
			cnt++;
		}
		else {
			for(int i = 1; i <= n; i++) {
				col[row + 1] = i;
				if(isPossible(row + 1)) {
					dfs(row + 1);
				}else {
					col[row + 1] = 0;
				}
			}
		}
		col[row] = 0;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i = 1; i <= n; i++) {
			col = new int[n + 1];
			col[1] = i;
			dfs(1);
		}
		System.out.println(cnt);
	}
}