백트래킹

사요·2021년 9월 29일

알고리즘

알튜비튜

목록 보기

7/16

모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice

📤백트래킹

완전탐색처럼 모든 경우를 탐색하나, 트리 구조를 기반으로 중간 과정에서 조건에 맞지 않는 케이스를 가지치기하여 탐색시간을 줄이는 기법
모든 경우의 수를 탐색하지 않기 때문에 완전 탐색보다 시간적으로 효율적임.
탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야하기때문에, 재귀를 사용하는 경우 많음.
조건을 어떻게 설정하고, 틀렸을 시 어떤 시점으로 돌아가야 할지 설계를 잘 하는 것이 중요

📼과정

어떤 노드의 유망성(promising)을 점검 -> 조건에 맞는지 안맞는지
유망하지 않다면 배제함( 가지치기)
해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 탐색

☸가지치기

지금의 경로가 해가 될 것 같지 않으면 (non-promising), 그전으로 되돌아 가는것 (back)
즉, 불필요한 부분을 쳐내는것
되돌아간 후 다시 다른 경로 검사
가지치기를 얼마나 잘하느냐에 따라 알고리즘의 효율성이 결정됨.

즉, 답이 될 만한지(promising) 판단하고, 그렇지 않다면 탐색하지 않고 다시 전으로 넘어가서(back) 탐색을 계속 하는 것

🎯DFS와 BT

: DFS와 Back-tracking 둘다 재귀 호출 형태로 자주 구현이 되기 때문에 헷갈린다.

두 알고리즘은 사용 목적에 차이가 있다.

DFS : 완전 탐색을 기본으로 하는 그래프 순회 기법으로, 모든 노드를 방문하는 것을 목표로 한다.

Back-tracking : 불필요한 경로를 차단하고, 이전 단계로 돌아와 다른 후보해를 탐색해 나가는 방법

=> 일단 가보고 후보해가 될 수 없으면 다음 단계로 진행하지 않고 되돌아 나온다.

📝재귀함수에 관한 이해

백트래킹 문제를 잘 풀기 위해서는 재귀함수에 대한 완벽한 이해가 필수적이다.

만일, 아래와 같은 재귀함수가 있다고 하자. 결과가 어떻게 될까?

void recursion(int n) {

	if (n == 1)
		return;
        
	cout << n <<"A"<<' ';

	recursion(n - 1);

	cout << n <<"B"<<' ';
	
	return;
}
int main() {

	recursion(4);

}

바로, 이러한 결과가 나온다.

여기서 알수있는 것들이 몇가지 있다.
1. B는 앞의 재귀 호출함수가 완전히 마쳐지기 이전까지 출력되지 않는다.
2. 여기서 재귀함수가 완전히 마쳐진다는 것의 의미는, 그 함수가 파고 들어 결국 return문을 만났다는 것을 의미한다.
3. return 문을 만나면 가장 깊은곳에 위치한 함수부터 차례대로 그 값을 돌려받는다.

이를 그림으로 나타내면 이렇다.

나는 처음에 6번 이후에 바로 9번 과정이 이어지는것이 아닌가 생각했었다. 하지만 그렇지 않았다. 재귀함수 호출은 스택구조를 취하기 때문에 즉, 깊은곳에 있는 과업이 우선 끝 마쳐져야 더 얕은곳(?)에 있는 과업이 리턴값을 돌려받으면서 나머지 문장을 실행할 수 있게 되는것이다.

🔭백트래킹 적용 상황

주로 재귀함수로 구현하기때문에 문제에서 주어지는 N의 크기가 작다! N<20
그 전 과정으로 돌아가면서 하는 탐색이 필요한 경우
check 배열을 많이 사용.

📗백트래킹 대표문제

BOJ) 15649 : N과 M

자연수 N,M이 주어졌을때 1~N까지 자연수 중 중복없이 M개를 고른 수열을 모두 구하라

1<=M<=N<=8

💡접근

제약조건을 살펴보자 -> 중복 X, 수열 길이가 M
재귀함수 설계 -> 각 수를 넣을때, 이미 수열 내에 있으면 넘어감(체크배열필요) ,기저조건은 길이가 M일때
해당 수가 현재 수열에서 사용이 되었는지 확인하는 배열필요 ->즉, 수를 인덱스로 가지는 체크배열. ->가지치기 역할

✨ 여기서 중요한 것은 백트래킹을 구현할때에는 부모노드로 돌아가기전(return문을 만나기전)에 꼭 조건을 원래 상태로 되돌려놓아야한다는 점이다. 그렇지 않으면 조건이 지속된채로 탐색이 이어져 원하지 않는 결과가 도출된다.

이를 그림으로 나타내면 이렇다.

👑N-Queen

# 백트래킹 정석
N X N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제

🔥 제한 사항

입력 범위는 1 <= N < 15

💡접근

퀸은 하나의 행 당 하나밖에 올 수 없다.
즉, 하나의 행씩 옮겨가면서 배치가능한 열을 탐색하자.
퀸을 열에 배치한 이후에는 세로,좌하향,우하향 대각선에 퀸을 배치할수 없음을 체크한다. -> 배열필요
이때 r을 행, c가 열이라고 한다면

check[c] : 세로 체크
check[c+r] : 좌하향 대각선 체크
check[c-r+n] : 우하향 대각선 체크

이 과정을 반복해주면, 아래그림과같이 퀸이 n개 존재할수있는 모든 경우의수를 모두 구해줄 수 있다. 구현방법에서 약간의 차이가 있지만 논리 흐름은 같다. 우리는 가로의 중복을 피하기위해서 행별로 퀸을 두었는데, 아래 그림은 열별로 퀸을 두는 경우의 수를 구한 모습이다.