DFS, BFS
깊이 우선 탐색 (DFS, Depth-First Search)
개념
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
- 즉 DFS에 백트래킹을 응용하여 모든 경우의 수를 찾을 수 있다.
- 즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색한다
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다.
- DFS는 비밀이야기
특징
- 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다.
- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다. (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.)
- DFS는 스택을 사용하여 구현할 수 있다.
과정
시간 복잡도
- DFS는 그래프(정점의 수 : N, 간선의 수 : E)의 모든 간선을 조회한다.
- 인접 리스트로 표현된 그래프 : $O(N + E)$
- 인접 행렬로 표현된 그래프 : $O(N^2)$
코드
/**
* 재귀 DFS - 인접행렬 이용
* @param a 인접행렬
* @param c 방문여부
* @param v 탐색을 시작할 정점 번호
* @param list DFS 결과를 담을 리스트
*/
public static void dfs(int[][] a, boolean[] c, int v, ArrayList<Integer> list) {
int n = a.length - 1;
c[v] = true;
list.add(v);
for (int i = 1; i <= n; ++i) {
if (a[v][i] == 1 && !c[i]) {
dfs(a, c, i, list);
}
}
}
/**
* 스택 DFS - 인접행렬 이용
* DFS는 사실 스택을 사용한다!
* @param a 인접행렬
* @param c 방문여부
* @param v 탐색을 시작할 정점 번호
* @param flag 방문여부flag
* @return
*/
public static int[] dfs(int[][] a, boolean[] c, int v, boolean flag) {
Stack<Integer> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
int n = a.length - 1;
stack.push(v);
c[v] = true;
list.add(v);
while (!stack.isEmpty()) {
int vv = stack.peek();
flag = false;
for (int i = 1; i <= n; i++) {
if (a[vv][i] == 1 && !c[i]) {
stack.push(i);
list.add(i);
c[i] = true;
flag = true;
break;
}
}
if (!flag) {
stack.pop();
}
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); ++i) {
answer[i] = list.get(i);
}
return answer;
}
/**
* DFS - 인접리스트 사용
* @param a 인접리스트
* @param c 방문여부
* @param v 탐색을 시작할 정점 번호
* @param list DFS 결과를 담을 리스트
*/
public static void dfs(ArrayList<Integer>[] a, boolean[] c, int v, ArrayList<Integer> list) {
if (c[v])
return;
c[v] = true;
list.add(v);
for (int vv : a[v]) {
if (!c[vv]) {
dfs(a, c, vv, list);
}
}
}
너비 우선 탐색 (BFS, Breadth-First Search)
개념
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
- 시작 정점을부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 즉 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 떄 이 방법을 선택한다
- ex. 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa사이에 존재하는 경로를 찾는 경우
- 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
- 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
- ex. 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa사이에 존재하는 경로를 찾는 경우
- BFS는 소문
특징
- BFS는 재귀적으로 동작하지 않는다.
- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다. 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다.
- 즉 선입선출(FIFO)원칙으로 탐색한다.
과정
-
깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.
코드
/**
* 큐 BFS - 인접행렬 이용
* @param a 인접행렬
* @param c 방문여부
* @param v 탐색을 시작할 정점 번호
* @return
*/
public static int[] bfs(int[][] a, boolean[] c, int v) {
Queue<Integer> q = new LinkedList<>();
List<Integer> list = new ArrayList<>();
int n = a.length - 1;
q.add(v);
c[v] = true;
while (!q.isEmpty()) {
v = q.poll();
list.add(v);
for (int i = 1; i <= n; ++i) {
if (a[v][i] == 1 && !c[i]) {
q.add(i);
c[i] = true;
}
}
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); ++i) {
answer[i] = list.get(i);
}
return answer;
}
/**
* BFS - 인접리스트 사용
* @param a 인접리스트
* @param c 방문여부
* @param v 탐색을 시작할 정점 번호
* @return
*/
public static int[] bfs(ArrayList<Integer>[] a, boolean[] c, int v) {
Queue<Integer> q = new LinkedList<>();
List<Integer> list = new ArrayList<>();
q.add(v);
c[v] = true;
while(!q.isEmpty()) {
v = q.poll();
list.add(v);
for (int vv : a[v]) {
if (!c[vv]) {
q.add(vv);
c[vv] = true;
}
}
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); ++i) {
answer[i] = list.get(i);
}
return answer;
}
}