DFS / BFS 기본 원리
이 글의 목차14개
DFS(Depth - First Search) 깊이 우선 탐색
BFS(Breadth - First Search) 너비 우선 탐색
계속 헷갈려서 글로 정리한다.
DFS : 특정 노드와 연결된 노드를 파고들어 더 이상 연결된 노드가 없을 때 까지 이동한다.
BFS : 특정 노드와 연결된 모든 노드를 확인하며 한 레벨씩 이동한다.
DFS는 끝 노드까지 확인하기 때문에 구현이 간단하지만, 모든 경우의 수를 확인해야 하는 경우 시간 복잡도가 증가할 수 있다.
BFS는 연결된 노드를 모두 확인하며 한 레벨 씩 확인하기 때문에 특정 조건에 도달하는 최소값을 찾는 경우에 DFS 보다 훨씬 좋은 성능을 보인다.
각각의 가장 기본형이 되는 코드를 작성하며 기본 코드 포맷을 외워보자.
DFS 조합
배열 [1, 2, 3, 4, 5] 에서 크기가 3개의 수를 뽑아 만들 수 있는 경우 출력.
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] number = {1, 2, 3, 4, 5};
int[] visited = new int[number.length];
int length = 3;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < number.length; i++) {
dfs(number, visited, length, i, list);
}
}
private static void dfs(int[] number, int[] visited, int length, int nowIndex, List<Integer> list) {
if (visited[nowIndex] == 1) return;
visited[nowIndex] = 1;
list.add(number[nowIndex]);
if (list.size() == length) {
System.out.println(list);
} else {
for (int i = 0; i < number.length; i++) {
dfs(number, visited, length, i, list);
}
}
visited[nowIndex] = 0;
list.remove(list.size() - 1);
}
}해당 코드에서 크게 중요한 부분은 3가지이다.
visited 배열
재귀함수 이해
백트래킹
visited 배열
각 인덱스는 0으로 초기화 되어, 리스트에 들어간 값의 인덱스는 1로 변환한다.
이후에 dfs함수를 재귀하며 리스트에 포함된 수인 경우를 무시하는 역할
2. 재귀함수
dfs 함수 내에서 for문을 통해 dfs를 다시 호출하여 재귀하게 된다.
해당 코드에서는 순열을 구하기 때문에 (조합 요소의 순서를 고려한다.)
nowIndex 보다 작은 인덱스를 탐험하기 위해 for문의 카운터를 int i = 0으로 설정하였지만,
순서를 고려하지 않는 조합의 경우에는 int i = nowIndex + 1로 설정하여 최적화할 수 있다.
3. 백트래킹
조건 (리스트의 크기가 3)을 만족할 때 visited의 기록을 지우고, 리스트에서 삭제해야한다.
이 코드는 dfs코드 마지막에 존재해야 한다.
현재 인덱스 (nowIndex) 에서 만들 수 있는 모든 경우의 수를 확인한 뒤 다음 인덱스로 넘어가야 하기 때문이다.