BFS, DFS와 트리, 그래프에 대한 글..

시작하기에 앞서, 기초적인 구현 방식, 정보들은 최대한 글에서 다루지 않을 예정이고, 혼동되거나 헷갈리는 부분들,
놓치고 넘어가기 쉬운부분들만 설명할 것임을 유의해주세요..!


그래프 탐색이 필요한 이유는 바로 선형적인 탐색 (for문을 통한 i:1~n) 으로 탐색하지 못하는 문제들을 탐색하기
위해서이다. 예를들어 그래프 탐색이 필요한 문제중 하나인 백준 2178 "미로 탐색" 을 보자.
우리는 점차 증가하는 인덱스를 통한 탐색이 아닌, 갈 수 있는 위치로 향하는 탐색을 해야하는데, 이는 for문과 적합하지
않다. 그렇기에 우린 이러한 갈 수 있는 방향을 "그래프" 로 만들어나가며 탐색을 해나가는 것이다.
그래프의 대략적인 정의는 정점, 그리고 간선으로 이루어진 대충 아래 그림 같은 친구들을 말한다.

그래프 예시

그래프는 보통 vector,arr 혹은 typedef를 통한 타입선언으로 구현하는데, 나는 vector을 통한 구현이 가장 편해 이를 통해 설명하겠다..

vector<pair<int,int>> vec[100]; 이는 벡터 배열로, 벡터의 각인덱스 (vec[0],vec[1].....vec[99]) 는 vector<pair<int,int>> 와 비슷한 역할을 하므로, 각 인덱스마다 int 타입 데이터를 누적하여 저장할 수 있게된다.
여기, u>v로 가는 비용이 w인 간선이 있다고 가정해보자. 우리는 이를
vec[u].push_back({v,w}); 이렇게 저장해줄 수 있다. vec[x] = vecor<pair<int,int>> 의 역할을하고, vec[x] 에 누적
되어있는 pair 값들은 {x에서 갈수 있는 정점, 가는 비용} 이 되는거다 ( pair 입력시 make_pair 을 많이들 쓰던데
{} 안에 넣어주면 간단하게 가능하다.)

그래프를 구현하는 법을 알았으니 bfs,dfs 에 대해 알아보자.

백번의 설명보단, 아래 링크를 보고 오면 둘의 차이가 명확하게 보일 것이다.
https://twpower.github.io/images/20180114_73/dfs-bfs-example.gif

 

 

여기서 더 나아가 dfs와 bfs를 언제 사용해야하는지에 대하여 자주 헷갈리는데, 쉽게 설명하자면 이거다.
대부분의 비선형 탐색은 bfs로 구현하라!

dfs가 주로 사용하는 재귀는 완성되었을 때의 코드는 짧지만, 디버깅하기 불편하고, dfs를 사용해야하는 경우는 적다. 하지만 bfs는 디버깅이 쉬우며, 사용해야하는 경우가 dfs보다 많다.

그렇다면 본론으로가서 위의 둘을 각각 언제 사용해야할까?

bfs: 단위거리인 상황(모든경로의 비용이 1로 일정)에서 "최단거리" 를 구할 때. >> 그러면 "단위길이" 가 아닌 최단거리는 어떻게 구해야할까...? 이건 나중에 최단거리에 대한 글을 따로 쓰겠지만, 다익스트라, 혹은 음수가중치가 존재할 경우
벨만포드를 사용해야한다. >> bfs는 깊이가 0인것,1인것, 2인것....... 이렇게 탐색해나가기 때문에 가장 먼저 나오는
조건값이 가장 낮은 깊이(깊이=출발지에서 목적지까지 거치는 간선 수) 즉, 최단거리이다.

여기서 다시 한번 위의 문제 2178번으로 돌아가 보자.
이 문제는 그래프를 탐색하는 문제이다.
우리는 보통 '어딘가에서 어디로 가야된다' 라는 상황에 놓여있다. 
우리는 출발지와 목적지가 정해져 있고, 어디서 어디로, 상하좌우로 움직이던 모든 비용은 1로 일정하다.
또한 이미 왔던 정점을 다시 방문해야할 필요도 없고, 오직 "목적지"로 향하는 것만이 목적이다.

아래는 그래프 탐색의 예시이다.

탐색 예시

최상위 노드 F는 시작점이고, F의 바로 아래에 존재하는 노드들은, F에서 갈수 있는 지점들이다. 이런식으로

어떤 노드의 하위 노드는 그 노드에서 갈 수 있는 지점을 나타내고,  깊이(출발지, 혹은 최상위 노드에서 몇번에 거쳐 갈 수 있는가)는 출발지에서 해당지점까지 몇번에 걸쳐서 갈 수 있는가 이다. bfs는 깊이가 낮은 것부터 순서대로 탐색해나가기 때문에, 탐색중 가장 먼저 찾아지는 도착지 = 도착지로 가는 최단거리가 된다. 이 매커니즘 때문에 단위길에서의 최단거리는 bfs를 쓰는 것이 보다 효율적이다. 

 

 

 

dfs:
1.깊이를 저장해야할때(bfs도 queue에 queue<pair<pair<int,int>,int> (<<도착지점,비용>,깊이> ) 를 통해
깊이 정보를 저장하고, 깊이를 한계단씩 내려갈 때마다 <<v,w>,현재깊이+1> 대충 요런식으로 깊이를 저장가능하기에 필수는 아니다. )

2.(중요) 경로를 알아야할 때. >> 한 경로씩 처음부터 끝까지 탐색하기에, 만족하는 조건이 나오면, 해당 탐색을 출력하면 그만이다.


이 외의 비선형탐색들은 앞서 설명한 디버깅 관한 문제로 bfs를 추천한다.

bfs, dfs 를 요약해서 정리하자면

1. 대부분의 비선형 탐색은 그래프를 만든 뒤, dfs, bfs로 탐색해준다.

2.dfs를 써야만 하는 케이스를 제외하면 bfs를 쓰자

3.dfs,bfs로 최단거리를 푸는 경우는 "단위길이" 일때 뿐이고, bfs로 구현해야한다! 가중치가 존재하는 그래프일시,
다익스트라, 벨만포드, 플로이드 와샬 과 같은 최단거리 알고리즘을 사용하자!

틀린 부분이나, 이해가 되지 않는 부분들은 댓글로 알려주세요..!