경로탐색 알고리즘 BFS, DFS

경로탐색 알고리즘 BFS, DFS

경로 탐색 알고리즘이란? 그래프에서 경로를 탐색하는 방식이다.

경로? A 지점에서 B지점으로 가는 길을 뜻한다. 

일상생활에 비교해보면 우리집에서 서울역까지 갈려면 2호선을 타고 4호선으로 갈아타도 되고, 버스를 타고 가도 되고, 버스를 타고 가다가 내려서 4호선을 타도 된다.

이처럼 다양한 경로가 존재하는데 그중에 원하는 조건을 만족하는 경로를 찾기 위해서 모든경우를 다 해보는데 이 때 쓰는 방식이 

DFS(깊이 우선 탐색)와 BFS(너비우선 탐색)가 있다.

DFS -> Depth First Search. BFS -> Breadth First Search.

BFS와 DFS의 문제는 (DFS와 BFS) - https://www.acmicpc.net/problem/1260

 

위 그래프를 탐색한다고 생각해보자. (그림 출처: 위키피디아)

1 번점에서 시작하여 중복되지 않게 모든 점을 탐색해보며 두가지 방식을 비교해보자. 

가장큰 차이점은 DFS는 재귀 ( Stack )를 사용하여 접근한다는 것이고, BFS는 Queue를 사용하여 접근한다는 것이다.

---

DFS

 

DFS로 탐색을 시작해보자. 

DFS는 일단 갈수있는 노드중의 한곳으로 간뒤. 그 곳에서 또 갈 수 있는 들리지 않은 노드중 한곳으로감. 계속 타고 드러가다 갈곳이 없으면 이노드로 들어오기전 노드로 돌아간뒤 거기서 다시 뻗어나갈 다른 방문한적 없는 노드가 있는지 확인한다.

1번 노드 을 넣고 시작한다. stack = [1]

1번 노드에서 갈 수 있는 노드를 아무거나 찾아 스택에 넣는다. ( 문제의 조건상 작은 번호 순으로 2번 노드를 택한다 ). stack = [1, 2].

2번 노드에서 갈 수 있는 노드를 찾아 스택에 넣는다. 중복되지 않은 가장 작은 수는 5,  stack = [1, 2, 5].

5번 노드에서 갈 수 있는 노드를 찾아 스택에 넣는다. 중복되지 않은 가장 작은수는 9, stack = [1, 2, 5, 9].

9번 노드에서 갈 수 있는 노드가 없다. 그러면 스택에서 9번 노드를 빼고. stack = [1, 2, 5]

그전에 방문한 5번 노드에서 다시 갈 수 있는 곳을 확인한다. 10번 노드로 간다. stack = [1, 2, 5, 10]

10번 노드에서 갈 수 있는 노드가 없다. 그러면 스택에서 10번 노드를 빼고, 그전에 방문한 5번 노드로 다시 돌아간다. stack = [1, 2, 5]

5번 노드에서 갈 수 있는 노드가 더 없다. 그러면 스택에서 5번 노드를 빼고, 그전에 방문한 2번 노드로 다시 돌아간다. stack = [1, 2]

2번 노드에서 6번 노드로 갈 수 있다. 6번 노드로 간다. stack = [1, 2, 6]

-- 중략 --

이런식으로 모든 노드를 검색하면된다. 이를 DFS라 하고 방문하는 점 순서대로 출력해보면 [ 1, 2, 5, 9, 10, 6, 3, 4, 7, 11, 12 8] 이다. 

stack을 재귀를 이용해서 구현 할 수 있는데. 

// 함수로 구현해보자면

// l[i][j] => i 노드와 j 노드가 연결 되어 있음.

// check[i] => i 노드가 들렸던 노드인지 아닌지.

// n => 총 노드의 수

void DFS(int now){

// now 노드에서 다른 노드로 갈 수 있는지 확인

printf("%d ", now);

int i;

for(i=1;i<=n;i++){   // now 에서 i 로 갈 때.

if(l[now][i] == true && check[i] == false){

check[i] = true;

DFS(i);

}

}

}

DFS(1);

---

BFS

BFS 로 탐색을 시작해보다. BFS 방식은 갈 수 있는 모든 노드를 큐에다가 넣는것이다.

그리고나서 큐의 앞부분을 빼면서 그 점에서 갈 수 있는 모든 노드를 들리면 된다.

시작점인 1번 노드를 큐에 넣는다. queue = [ 1 ]

맨 앞 노드인 1번 노드를 빼며 1번 노드에서 갈 수 있는 모든 노드중  방문하지 않은 노드를 큐에 추가한다. queue = [ 2, 3, 4 ]

맨 앞 노드인 2번 노드를 빼며 2번 노드에서 갈 수 있는 모든 노드중 방문하지 않은 노드를 큐에 추가한다. queue = [ 3, 4, 5, 6 ]

맨 앞 노드인 3번 노드를 빼며 3번 노드에서 갈 수 있는 모든 노드중 방문하지 않은 노드를 큐에 추가한다. queue = [ 4, 5, 6 ]

이런식으로 하면된다. 결국 [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] 순으로 방문 하게 된다.

즉 가까운 점 부터 방문하게 되는것이다. 이를 구현해보면

// l[i][j] => i 노드와 j 노드가 연결 되어 있음.

// check[i] => i 노드가 들렸던 노드인지 아닌지.

// n => 총 노드의 수

void BFS(){

Queue<int> queue;

queue.push_back(1);

int now, i;

while( queue.size() != 0){

now = queue.pop_front(); //큐의 맨 앞점을 뺀뒤

printf("%d ",now);

for(i=1;i<=n;i++){ // 갈 수 있는 점을 찾아서 감.

if(check[i] == false && l[now][i] == true){ //갈 수 있는데 안들렸다면

check[i] = true; // 들렸다고 표시해줌.

queue.push_back(i); // 큐에 i 노드를 추가함.

}

}

}

}

BFS();

---

간략하게 알아봤지만. BFS, DFS는 경우의 수를 탐색하던 경로를 탐색하던 정말 유용한 알고리즘이다.