Back Tracking

본 게시글은 권오흠 교수님의 영상과 여러 블로그들을 공부하고 정리한 글 입니다.

 

 

[ Back Tracking ]

 

 

'백 트랙킹' 이러니깐 사실 어떤 알고리즘인가 와 닿지가 않았는데 '되추적' 이라고 하니깐 확 와닿았다.

 

예상 되듯이 완전 탐색의 일종인데, 완전 탐색이 모든 경우의 수를 탐색하는 것이라면,

백 트랙킹은 탐색을 하는 도중 지금 경로가 답이 될 것 같지 않다면 그 경로를 더 이상 가지 않고 되돌아 가는 기법을 말한다.   반복문을 줄이기 때문에 더 효율적일것이라고 추론 할 수 있다.

( 사실 대표적인 완전 탐색인 DFS도 탐색을 하다가 if 문으로 조건 걸어주기만 한다면 다시 되돌아 올 수 있어서, 정확히 둘의 차이점은 잘 모르겠다.. )

 

DFS 와 백트랙킹의 정확한 차이점을 찾아보다 어떤 블로그 분의 좋은 글을 보게 됐는데 백트랙킹을 이해하는데 많은 도움이 됐다.

백트래킹(backtracking)이란?
솔루션을 찾는 과정에서, 유망(promising)하지 않은 후보해에 대해 대해 빠르게 포기하고 이전 단계로 되돌아(back track)가 다른 후보해를 찾는 알고리즘 기법이다.

DFS는 기본적으로 그래프 형태 자료구조에서 모든 정점을 탐색할 수 있는 알고리즘 중 하나이다. 깊이를 우선적으로 탐색하기에 재귀 또는 스택을 이용한다.

DFS 는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동한다. 하지만 DFS 는 모든곳을 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할수도 있다.

그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 백트래킹은 DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법이다. 가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화 될 수 있는 방법이다.

DFS는 기본적으로 모든 노드를 탐색하는 것이 목적이지만,
상황에 따라서 백트래킹 기법을 혼용하여 불 필요한 탐색을 그만두는 것이 가능하다. 

즉, DFS와 백트래킹은 유사한 부분이 있으며 기본적으로 사용 목적이 다르지만 두 기법을 혼용하여 사용하는 것이 가능하다.
완전히 다른 개념이 아니라 재귀 호출을 통한 기법 중 하나 이기 때문이다.

 

그럼 문제를 보고 이게 Back Tracking 이겠다 라고 어떻게 알 수 있을까?

보통 Back Tracking 문제 같다 싶으면 상태 공간 트리 를 생각하면 된다.

문제를 읽고 주어진 테스트 케이스를 시뮬레이션 해보면서 이해하다가 내가 상태 공간 트리를 사용하면서 경우의 수를 계산 하고 있다? 싶으면 백 트랙킹 의심해봐야 한다. 물론 백 트랙킹 문제의 많은 경우가 DP로도 풀린다고 한다.

그러나 아직 백트랙킹으로만 풀리는 문제들이 종종 있다고 한다.

 

 

백문이 불여일코  : 백번을 들어도 한번 코딩 해보는것만 못하다.

( 이 말 좋은것 같다. 블로그 이름도 이걸로 바꿔야겠다 :) )

 

자!  그럼 대표적인 백트랙킹 문제인 N-Queen 문제를 풀어보자.

 

---

 

https://www.acmicpc.net/problem/9663​

9663번: N-Queen

https://programmers.co.kr/learn/courses/30/lessons/12952?language=cpp 

코딩테스트 연습 - N-Queen

---

[ 최종 구현 ]

재귀로 구현하려면 아래와 같은 수도코드 형식을 띄는게 가장 간단하면서도 명확하다.

 

---

[ 코드 ]

#include<iostream>
#include<vector>

using std::cin; using std::cout;

int n, answer;
int cols[16];

bool promising(int level) {  // 대각선, 세로에 다른 퀸 없는지 검사.
	if (level == 1)return true;  // 첫번째 퀸은 어디든 가능.
	for (int i = level - 1; i >= 1; i--) { // 현재 레벨 전 퀸들 전부 검사.
		// 대각선 검사. ( 두 지점 가로 차이랑 = 세로 차이랑 같으면 대각선.
		if (std::abs(cols[level] - cols[i]) == (level - i)) {
			return false;
		} // 세로 검사.
		else if (cols[i] == cols[level]) {
			return false;
		}
	}
	return true;  // 전부 검사했는데도 false 안되면 true;
}

void nQueen(int level) {
	
	for (int i = 1; i <= n; i++) {
		cols[level] = i;

		if (promising(level)) { // cols[level]이 i가 될 수 있다면
			if (level == n) {
				answer++;
				return;
			}
			nQueen(level + 1);
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	int level = 1;
	nQueen(level); // 1 부터 시작.
	cout << answer;
	return 0;
}

< 백 트랙킹 문제  >

https://www.acmicpc.net/step/34

 

---

 

[ Reference ]

 

 

 

https://thd0011.tistory.com/19

[알고리즘] 백트래킹 (Backtracking) 알고리즘

https://hongjw1938.tistory.com/88

알고리즘 - 백트래킹(Backtracking)

https://bunnnybin.tistory.com/entry/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-Backtracking-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%B4%EB%9E%80

백트래킹 (Backtracking) 알고리즘이란?