<PART 2> DFS/BFS

- DFS (Depth-First Search, 깊이 우선 탐색)
그래프에서 깊은 부분을 우선적을 탐색하는 알고리즘입니다.  즉 최대한 멀리있는 노드부터 탐색하는 방법입니다.
여기서 그래프를 표현하는 방법이 2가지가 있습니다. 

1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
2. 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식

대략적으로 설명하면
ex)       (0)
      | 7       |5
    (1)          (2)
형태의 그래프가 존재한다고 가정합니다.

노드	0	1	2
0	0	7	5
1	7	0	무한
2	5	무한	0

인접행렬은 2차원 배열로 각 노드가 연결된 형태로 기록하는 방식입니다, 연결되지 않았을 경우는 무한의 비용이라고 작성합니다.
ex)
INF = 999999999 #무한의 비용 선언 
graph = [
           [0,7,5],
           [7,0,INF],
           [5,INF,0]
]

인접 리스트는 모든 노드에서 연결된 노드에 대한 정보를 차례대로 연결하여 저장합니다.
ex)
graph = [ [(1,7),(2,5)],[(0,7)],[(0,5)]}

이렇게 표현이 가능합니다.
보편적으로 인접행렬은 원하는 노드가 연결되어있는지 한 눈에 확인할 수 있다는 장점이 있고 모든 노드를 다 적기 때문에 오래 걸린다는 단점이 있습니다. 아닌 경우도 존재합니다.

- DFS
그렇다면 DFS는 어떤 과정을 거칠까요?
보통 최상단 노드에서 가장 낮은 숫자,알파벳부터 시작합니다.
1. A에서 B,C를 갈 수 있으나 낮은 B부터 갑니다.  A,B
2. B와 인접한 노드 중 D,E중 낮은 D로 갑니다. A,B,D
3. H로 갑니다. A,B,D,H
4. H에서 인접한노드가 없으므로 H를 뺍니다. A,B,D
5. D에서 H,I중에 고민하였으므로 I로 갑니다. A,B,D,I
6. 인접한 것이 없으므로 뺍니다. A,B,D
7. B에서 E로갑니다. A,B,E
8. J로 갑니다. A,B,E,J
9. 인접한 노드가 없을 경우 다 뺍니다. A
10. C로 값니다. A,C
11. F와 G중 F가 작으므로 F로 갑니다. A,C,F
12. G로 갑니다. A,C,G
13. A,C
14. A
15. 없음
최종적으로 먼저 스택에 들어간 순서는 다음과 같습니다.    [A, B, D, H,  I,  E,  J,  C,  F,  G]
이처럼 스택처럼 마지막에 있는 것이 빠지고 채워지기 때문에 DFS는 스택자료구조입니다.

이처럼 알파벳 A~G를 1~10으로 표현하면 위에 적은 순서대로 표시되게 됩니다. 
이 같은 알고리즘을 깊이 우선 탐색 DFS라 합니다.
 
- BFS (Breath First Search, 너비우선탐색)
가까운 노드부터 탐색하는 알고리즘입니다.
이를 위해서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 

먼저들어온것이 나가는 것만 기억하자. 
1. A가 들어온다. A
2. A가 나가고 A가 인접한 B,C가 모두 들어온다. B,C
3. 먼저 들어온 B가 나가고 D,E가 들어온다. C,D,E
4. C가 나가고 F,G가 들어온다. D,E,F,G
5. D가 나가고 H,I가 들어온다. E,F,G,H,I
6. E가 나가고 J가 들어온다. F,G,H,I,J
7. F와 근접한 노드가 없다. G,H,I,J
8. 나머지도 마찬가지다. 없음
최종적인 순서는 다음과 같습니다. A,B,C,D,E,F,G,H,I

BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단합니다. 실제로 구현함에 있어서 deque라이브러리를 사용하는 것이 좋습니다.

- DFS/BFS 정리

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용