DFS(Depth-First Search) 와 BFS(Breadth-First Search)는 그래프나 트리에서 노드를 탐색하는 두 가지 주요 알고리즘이다. 각각의 방식에는 특성이 있다.
DFS(Depth-First Search, 깊이 우선 탐색)
DFS는 스택을 사용한다. 스택을 사용하지 않고 재귀로도 구현이 가능하다. 재귀가 스택의 자료구조 원리를 사용하기 때문에 가능한 것이다. 트리 순회(전위순회, 중위순회, 후위순회, 루트노드)의 위치에 따라 이름이 붙여진다.
package study.blog.codingnojam;
import java.util.Stack;
public class Study_DFS_stack {
// 방문처리에 사용 할 배열선언
static boolean[] vistied = new boolean[9];
// 그림예시 그래프의 연결상태를 2차원 배열로 표현
// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
// DFS 사용 할 스택
static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) {
// 시작 노드를 스택에 넣어줍니다.
stack.push(1);
// 시작 노드 방문처리
vistied[1] = true;
// 스택이 비어있지 않으면 계속 반복
while(!stack.isEmpty()) {
// 스택에서 하나를 꺼냅니다.
int nodeIndex = stack.pop();
// 방문 노드 출력
System.out.print(nodeIndex + " -> ");
// 꺼낸 노드와 인접한 노드 찾기
for (int LinkedNode : graph[nodeIndex]) {
// 인접한 노드를 방문하지 않았을 경우에 스택에 넣고 방문처리
if(!vistied[LinkedNode]) {
stack.push(LinkedNode);
vistied[LinkedNode] = true;
}
}
}
}
}알고리즘 방식
1. 시작노드를 스택에 삽입하며 시작한다
2, 스택의 최상단 노드를 확인한다.
3. 최상단 노드에게 방문하지 않은 노드가 있으면 그 노들르 스택에 넣고 방문처리한다.
4. 최상단 노드에게 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 뺀다.
BFS(Breadth-First Search, 너비 우선 탐색)
DFS는 스택으로 했다면 BFS는 큐로 한다. 즉 가까운 것 위주로 탐색하는것이다. 이러한 특징 때문에 '최단경로'를 찾는 문제에서 주로 사용한다.
package study.blog.codingnojam;
import java.util.LinkedList;
import java.util.Queue;
public class StudyBFS {
public static void main(String[] args) {
// 그래프를 2차원 배열로 표현해줍니다.
// 배열의 인덱스를 노드와 매칭시켜서 사용하기 위해 인덱스 0은 아무것도 저장하지 않습니다.
// 1번인덱스는 1번노드를 뜻하고 노드의 배열의 값은 연결된 노드들입니다.
int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
// 방문처리를 위한 boolean배열 선언
boolean[] visited = new boolean[9];
System.out.println(bfs(1, graph, visited));
//출력 내용 : 1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7 ->
}
static String bfs(int start, int[][] graph, boolean[] visited) {
// 탐색 순서를 출력하기 위한 용도
StringBuilder sb = new StringBuilder();
// BFS에 사용할 큐를 생성해줍니다.
Queue<Integer> q = new LinkedList<Integer>();
// 큐에 BFS를 시작 할 노드 번호를 넣어줍니다.
q.offer(start);
// 시작노드 방문처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.isEmpty()) {
int nodeIndex = q.poll();
sb.append(nodeIndex + " -> ");
//큐에서 꺼낸 노드와 연결된 노드들 체크
for(int i=0; i<graph[nodeIndex].length; i++) {
int temp = graph[nodeIndex][i];
// 방문하지 않았으면 방문처리 후 큐에 넣기
if(!visited[temp]) {
visited[temp] = true;
q.offer(temp);
}
}
}
// 탐색순서 리턴
return sb.toString() ;
}
}
알고리즘 방식
1. 큐에서 하나의 노드를 꺼낸다
2. 해당 노드에 연결된 노드 중, 방문하지 않은 노드를 방문하고 차례대로 큐에 삽입 후 방문 한다.
위의 그림 처럼 DFS 는 스택의 형식으로 BFS는 큐의 형식으로 저장이 되는 방식이다.
Script
Stack 과 Queue 를 생각하면 LIFO (Last In First Out) 과 FIFO(Frist In first Out) 를 생각이 든다. Stack은 쌓아 올린다는 이미지가 있고 Queue는 줄을 서서 기다리는 의미지가 있는데 이것을 그래프에 대입해서 풀어야한다. 만약 그래프의 문제가 나오면 먼저 Stack과 Queue를 생각하고 Stack는 DFS Queue는 BFS라고 바로 생각이 나야한다. 그리고 각각의 특징에 대해서 잘 생각을 해야한다. 여러 문제를 풀면서 도입하는 연습을 많이 해야겠다.