그래프 탐색 - DFS vs BFS

1. 경로 찾는 문제가 나온다면..?

방법은 2개가 있다

• 1) 더 이상 탐색할 노드 없을 때 까지 탐색해본다. 더 이상 탐색할 노드 없으면 최근 방문 노드로 되돌아가서 가지 않은 노드 방문한다
• 2) 현재 위치에서 가장 가까운 노드 모두 싹 돌고, 다음 노드로 넘어감. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문

이게 뭐냐? 각각 깊이 우선 탐색, 너비 우선 탐색임

이해가 쉽도록 아래 그림을 확인해보자.

1.1. 깊이 우선 탐색

A-> B -> D

D에서 B로 되돌아 온다음 E로

E에서 B로 되돌아가 A로 되돌아가 C로 간다

 

1.2. 너비우선탐색

A에서 가장 가까운 B, C방문

B에서 가장 가까운 D,E

2. 코테 풀 때!!!

• 탐색은 해야하는데 최단 경로 구하는 거 아니면 DFS 쓰면 됨
• 최단 경로 찾는다? BFS 갈겨~~~~