1260 DFS와 BFS

입력값 :

4 5 1

1 2

1 3

1 4

2 4

3 4

 

- DFS (Depth First Search 깊이우선탐색)

• 한 방향으로 갈 수 있는 끝까지 탐색을 마치고, 그 다음 방향으로 탐색한다.

1. 길이 여러개일 경우 숫자가 작은 정점부터 탐색하므로 1 -> 2 로 이동.
2. 한 방향으로 탐색을 이어가야 하므로 1 -> 2 -> 4 -> 3  으로 이어진다.
3. 마지막 3 에 도착했을 때, 1 과 4는 이미 방문 한 상태이므로 재귀로 호출된 스레드가 하나하나 모두 종료된다. 
4. 모든 정점을 방문 했으므로 프로그램은 종료된다.

 

- BFS (Breath First Search 너비우선탐색)

• 한 정점에 도착했을 때, 그 정점에서 방문 가능한 정점은 모두 방문한다. 동시에 여러 정점을 방문하는 형태이다.
• 각 정점의 거리가 1일 때, 최단거리를 찾기 위해 사용한다.

이해를 위해 정점을 추가하였다.

1. 정점 1에서는 2 부터 4 까지 방문이 가능하다. (for문을 돌며 큐에 저장) --> 방문 1 | 큐 [2, 3, 4]
2. deque를 할 때 마다, 해당 정점에서 방문 가능한 정점들을 큐에 쌓는다.
   1. --> 방문 2 | 큐 [3, 4, 5]
   2. --> 방문 3 | 큐 [4, 5]
   3. --> 방문 4 | 큐 [5,6]
   4. --> 방문 5 | 큐 [6]
   5. --> 방문 6 | 큐 []
3. 프로그램 종료