[Algorithms] BFS, DFS 알고리즘
[Algorithms] BFS, DFS 알고리즘
안녕하세요? 정리하는 개발자 워니즈입니다. 이번시간에는 기본 알고리즘중 하나인 BFS, DFS 알고리즘에 대해서 정리를 해보도록 하겠습니다. 그래프의 모든 노드를 방문하는 알고리즘으로, 면접시에도 많이 나오는 내용이라 필히 알아둬야 할 내용입니다 .
1. DFS 알고리즘
Depth First Search의 의미로, 스택을 기반으로 계속해서 깊게 다음노드로 들어가서 검색을 하는 알고리즘입니다. depth아래로 더이상 내려갈 공간이 없으면, 상위의 스택에서 다음 노드가 있는지 검색을 수행하게 됩니다. 이런식으로 수행하는 방식이 바로 DFS 알고리즘입니다.
DFS알고리즘을 구현하기 위해서는 2개의 variable이 필요합니다.
- map : 2차원 배열로 인접 행렬 방식으로 두 노드간의 연결 정보를 나타냅니다.
- visit : 1차원 배열로 노드의 방문을 표기하게 됩니다.
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
map[from][to] = 1;
map[to][from] = 1;
}
input정보는 위와 같이 받게 됩니다. 양방향 행렬로 from, to 를 받습니다.
public static void dfs(int src) {
visit[src] = 1;
System.out.printf(src + " ");
for (int i = 1; i <= V; i++) {
if (visit[i] == 0 && map[src][i] == 1) {
dfs(i);
}
}
}
실질적으로 위와 같이 dfs 함수를 작성합니다. dfs의 동작 방식은, 조건에 맞는 노드가 있으면 해당 노드로 계속해서 스택을 쌓으면서 움직이는 것입니다.
가령 1번 노드에서 시작을 하게 되면, 1번 노드와 연결되어있는 다음 노드를 map 인접 행렬에서 찾습니다. 찾고 난다음에는 해당 노드로 다시 dfs함수를 스택으로 쌓으면서 이동하게 됩니다.
2. BFS 알고리즘
Breadth-First Search로 알려진 너비 우선 탐색에 대한 알고리즘입니다. 루트노드로부터 시작해서 다음 으로 연결된 모든 노드를 순차적으로 방문을 하는 방식입니다. 그래서 depth별로 각층에 해당 하는 노드를 모두 탐색한 뒤, 더 깊은 depth로 들어가는 방식입니다.
BFS는 위에 보시는 것처럼 루트노드를 시작으로 다음 Depth로 이동하면서 각 층에 모든 노드에 대해서 방문을 수행합니다.
BFS 알고리즘을 구현하기 위해서는 역시 2개의 variable이 필요합니다.
- map : 2차원 배열로 인접 행렬 방식으로 두 노드간의 연결 정보를 나타냅니다.
- visit : 1차원 배열로 노드의 방문을 표기하게 됩니다.
DFS와 동일하게 input정보는 받게 됩니다.
public static void bfs(int src) {
q.offer(src);
visit[src] = 1;
while (!q.isEmpty()) {
int x = (int) q.poll();
visit[x] = 1;
System.out.printf(x + " ");
for (int i = 1; i <= V; i++) {
if (visit[i] == 0 && map[x][i] == 1) {
q.offer(i);
visit[i] = 1;
}
}
}
}
BFS 알고리즘은 위와 같이 queue를 이용하게 됩니다. queue에서 뽑아서, 인접 행렬에 연결된 방문하지 않은 노드를 탐색하게 됩니다. dfs와 다른것은 방문을 하고 바로 이동하는 것이 아니라, 해당 depth에서 방문하지 않은 모든 노드를 탐색하게 됩니다. 그리고나서 while문을 통해서 바로 다음 depth로 이동하게 됩니다.
3. DFS 와 BFS 차이점
우선 DFS/BFS 같은 경우 다음과 같은 시간 복잡도를 갖고 있습니다 .
- 인접 리스트로 표현된 그래프 : O(V+E)
- 인접 행렬로 표현된 그래프 : O(V^2)
DFS의 장점으로는 BFS보다 찾고자 하는 정점이 depth가 깊게 있는데서 유리합니다.
BFS의 장점으로는 최단경로에서 이용할 수 있는 알고리즘입니다.
