BackTracking, DFS, BFS

BackTracking

"퇴각검색(backtrack)"

Backtracking(퇴각검색)이란 한정 조건을 가진 문제를 해결하는 전략이다.
- 출처 : wikipedia - 

 

이번에 알고리즘 스터디를 진행하면서 가장 먼저 접한 내용이 backtracking이다.

 

backtracking은 "한정 조건내의 모든 경우의 수를 고려하는 알고리즘" 이다.

 

구조적을 깊이우선탐색(DFS)를 기반으로 한다.

 

하지만 DFS는 모든 경우의 수를 다 구하기 때문에 굳이 한정 조건이 존재하는 환경에서는 비효율적이다.

 

그래서 이와 같이 조건에 부합하지 않는 수를 무시하고 조건을 만족하는 수를 구하는 방법이 백트래킹 알고리즘이다.

 

그렇다면 여기서 말하는 깊이우선탐색-DFS는 무엇일까?

 

---

 

Depth-First Search

"깊이우선탐색(DFS)"

맹목적 탐색 방법의 하나로, 어떠한 정점을 확인한 후 연결된 정점들 중 가장 우선순위가 높은 하나를 선택해 탐색해 나가며 더 이상 탐색할 곳이 없으면 이전상태로 되돌아가는 탐색방법.
- 출처 : wikipedia - 

 

예를 들어보자

 

아래의 트리구조를 보면

 

 

이를 A부터 시작하고 알파벳순으로 운선순위를 선정할때, DFS 결과를 보면

A-B-C-D-E-F-G-H 가 된다.

 

자세히 살펴보자

DFS는 "어떠한 정점을 확인한 후 연결된 정점들 중 가장 우선순위가 높은 하나를 선택해 탐색해 나가며 더 이상 탐색할 곳이 없으면 이전상태로 되돌아가는 탐색방법" 이다.

 

우선순위는 알파벳순이고 A노드부터 탐색을 시작한다.

A부터 시작할때, A는 첫 분기를 만난다. B 또는 D로 탐색을 해야하는데 여기서 우선순위가 알파벳 순이므로 B로 탐색한다.

B에서는 C로 가는 결과 밖에 없으므로 A->B->C 가 된다.

 

C에서는 분기가 B로 되돌아가며, B에서 갈 수 있는 분기를 모두 갔으므로 다시 A로 돌아가며 다시 분기문 선택에서 B는 이미 탐색을 했으니 D로 간다.

A->B->C->D

D에서의 분기도 알파벳 우선순위로 인해 E로 간다.

A->B->C->D->E

E에서의 분기도 알파벳 우선순위로 F로 가며 

A->B->C->D->E->F

F에서 분기가 없으므로 E로 되돌아가고 E에서 남은 분기인 G로 간다.

A->B->C->D->E->F->G

다시 G에서 E로 E에서 D로 분기를 다 돌았으므로 되돌아간다.

그리고 D에서 남은 분기인 H로 간다.

A->B->C->D->E->F->G->H

이렇게 DFS 탐색 결과를 확인할 수 있다.

 

이를 자세히보면 스택과 비슷하다고 느낄 수 있다.

실제 분기 과정을 스택과 유사하게 구상하면 다음과 같다.

 

A->B->C

A->B->C->D->E->F

A->B->C->D->E->F->G->H

실제 DFS를 코드상으로 구현할때 스택(Stack)을 활용한다. (방문하는 순서대로 스택을 쌓고, 끝나면 pop)

구현할 때는 스택뿐만 아니라 재귀로도 구현이 가능하다.

DFS와 비슷한 맹목적 탐색 방법의 하나로 BFS도 있다.

 

---

 

Breadth-First Search

"너비우선탐색(BFS)"

맹목적 탐색 방법의 하나로,
어떠한 정점을 확인한 후 연결된 정점들 중 인접한 모든 정점들을 우선 방문하는 탐색 방법.
더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용.
- 출처 : wikipedia - 

 

DFS와 똑같이 예를 들어보면

이를 A부터 시작할때, BFS 결과를 보면

A-B-D-C-E-H-F-G가 된다.

자세히 살펴보자.

 

BFS는 "어떠한 정점을 확인한 후 연결된 정점들 중 인접한 모든 정점들을 우선 방문하는 탐색 방법" 이다.

우선순위는 알파벳순이고 A노드부터 탐색을 시작한다.

 

A부터 시작할때, A는 첫 분기를 만난다. A와 가장 인접한 정점은 B와 D이다.

그러므로 B를 탐색하고 곧바로 D를 탐색한다.

A->B->D

그 후, B를 탐색한다. B와 인접한 정점은 C밖에 없다.

C와 인접한 정점은 없고 B와 인접한 정점을 모두 탐색했으므로 D와 인접한 정점을 탐색한다.

D와 인접한 정점은 E와 H가 있다.

A->B->D->C->E->H

이제 E를 탐색하는데 E와 인접한 정점은 F와 G가 있다.

A->B->D->C->E->H->F->G

F와 G와 인접한 정점은 없고 H도 인접한 정점이 없으므로 탐색결과는

A->B->D->C->E->H->F->G가 된다.

 

BPS를 구현하기 위해서 큐를 사용하는데, 이를 큐로 구상하면 다음과 같다.

 

A를 탐색한 후 A와 인접한 정점인 B와 D를 큐에 넣어주면서 A를 pop한다.

그 후, B와 인접한 정점인 C를 큐에 넣어주면서 B를 pop 한다.

그 후 D와 인접한 정점인 E와 H를 큐에 넣어주면서 D를 pop한다.

A->B->D

 

C와 인접한 정점이 없으므로 C를 pop하고 E와 인접한 F, G를 큐에 넣어준 후, E를 pop한다.

A->B->D->C->E

그 후, H와 인접한 정점이 없으므로 H를 pop하고 F,G와 인접한 정점이 없으므로 이 둘도 pop 한다.

A->B->D->C->E->H->F->G

이렇게 큐로 BFS를 구현했을때, pop하는 순서로 탐색 결과를 확인할 수 있다.

 

---

 

DFS와 BFS의 차이

DFS와 BFS의 차이점이라기 보다는 해당 탐색 방식이 더 잘 어울리는 부분이 어딘지 이해하는 것이 중요 것 같다.

정확하게 차이점이라 얘기하면 구현상, 스택이냐 큐이냐 의 차이인 것 같다.

 

DFS는 가중치에 대해서 지속적인 관리를 할 수 있다는 장점이 있다.

그래서 탐색에 대한 제약(조건) 등이 있을때 DFS로 구현하는 것이 좋다.

(솔직히 말하면 코드 구성이 더 편리하다.)

또한 모든 경로를 다 탐색해야하는 경우에 사용하는 것이 좋다.

 

BPS는 현재 나의 위치에서 가장 가까운 정점을 먼저 방문하는 것이 특징이다.

그래서 최단 거리/최소 비용들을 구하거나, 가중치가 1이거나, 탐색해야하는 비용이 적을 때 사용하는 것이 좋다.

 

---

 

 

다시 처음으로 돌아가서

BackTracking

"한정 조건내의 모든 경우의 수를 고려하는 알고리즘" 

백트레킹을 살펴보자

모든 경우의 수를 고려하는 것이니 DFS를 사용하고

이에 조건을 걸면 된다.

 

즉 DFS로 탐색할때, 다음 탐색하는 정점이 한정 조건내에 포함되는지 검사를 하고

"TRUE" 이면 해당 정점을 탐색하고 "FALSE" 이면 해당 정점을 탐색하지 않게 하면 된다.

백트레킹 알고리즘을 사용할 경우, 단순 DFS에서보다 훨씬 속도가 빨라질 것 같다.

 

---

 

백준 문제집에 보면 N-Qeen이라는 문제가 있다.

 

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

이를 백트래킹 알고리즘으로 풀었을때 코드는 다음과 같다.

 

//
//  main.cpp
//  nqeen
//
//  Created by 조우석 on 03/08/2019.
//  Copyright © 2019 j0dev. All rights reserved.
//
#include <iostream>
#include <cmath>


int count = 0;
int *arr;
int num;

void getQeenPos(int a);
bool checkFalse(int b);

int main(int argc, const char * argv[]) {
    
    std::cin >> num;
    arr = new int [num];
    getQeenPos(0);
    std::cout << count << std::endl;
    delete arr;
    return 0;
    
}





void getQeenPos(int a){
    //맨 밑에 열까지 내려가서 마지막 a++값이 num 과 같으면 count ++
    if(a == num) {
        count += 1;
    } else {
        for (int i=0; i<num; i++) {
            arr[a] = i;
            //배열 0번째 인덱스 첫번째 == (1,1) 검사 후, false면 0번째 인덱스 두번째 (1,2)
            //참이면 (1,1) 오케이 1번째 인덱스 1번째 검사 (2,1)
            if (checkFalse(a)){
                getQeenPos(a+1);
                //참일경우 각각 배열 arr에 인덱스별로 해당 값 저장
                // count 될 경우 가장 최근 분기문으로 넘어감
            }
        }
    }
}


bool checkFalse(int b){
    for (int i = 0; i<b; i++){
        //같은 열 검사 및
        if(arr[i] == arr[b]){
            return false;
        }
        if (abs(arr[i]-arr[b]) == (b-i)){
            return false;
        }
    }
    return true;
}