DFS
출처) https://developer-mac.tistory.com/64
1) 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다.
대표적으로 백트래킹(모든 경우의 수를 전부 고려하는 알고리즘)에 사용한다.
2)자기 자신을 호출하는 순환 알고리즘이다.
따라서 스택 또는 재귀함수로 구현할 수 있다.
3)일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.
4) 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 점이다. 이를 검사하지 않을 경우 무한루프에 빠질 수 있다.
사용 알고리즘
- 재귀함수
- 스택
시간 복잡도
인접 행렬 : O(V^2)
인접 리스트 : O(V + E)
장단점
DFS 장점
노드들을 방문할 때 마다 스택에 저장하므로, 현 경로상의 노드를 기억한다. 때문에 적은 메모리를 사용한다.
찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다.
DFS 단점
해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색한다. (메모리 소비 大)
효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다.
또한 DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없다.
DFS는 해에 도착하면 탐색을 종료하기 때문이다.
언제 사용하면 좋을까?
a. 경로의 특징을 저장하면서 탐색해야 할 때: DFS는 경로를 추적하면서 문제를 해결하는 경우에 유용하다. 예를 들어, 미로 찾기 문제에서 하나의 경로를 끝까지 탐색한 후에 다른 경로를 탐색한다.
b. 모든 노드를 방문하는 것이 중요할 때: 트리나 그래프의 모든 노드를 방문해서 정보를 수집하거나 검색할 때 사용된다.
c. 사이클이나 연결 요소와 같은 구조적 특성을 파악할 때: 그래프의 사이클 유무 확인, 연결 요소(Connected Components) 파악 등에 사용된다.
코드
// dfs, 재귀, 인접 행렬, i 정점부터 시작한다.
public static void dfs(int i) {
visit[i] = true;
// 노드 중복 접근 방지를 위한 방문 체크 배열. (boolean)
System.out.print(i + " ");
// j는 dfs 배열의 새로운 분기를 뜻한다.(int)
for(int j=1; j<n+1; j++) {
if(map[i][j] == 1 && visit[j] == false) {
dfs(j);
}
}
}BFS
출처) https://developer-mac.tistory.com/64
1) root node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다.
2) BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용한다.
3) 재귀적으로 동작하지 않는다.
4) 이 알고리즘 또한, 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 수 있다.
장단점
BFS 장점
답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.
BFS 단점
경로가 매우 길 경우에는 탐색 가지가 급격하게 증가하므로, 많은 기억 공간을 필요로 하게 된다.
해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.
사용 알고리즘
Queue
시간 복잡도
인접 행렬 : O(V^2)
인접 리스트 : O(V + E)
(DFS,BFS의 시간복잡도는 동일하다. 단, 평균적인 속도 자체는 BFS가 더 빠름.)
언제 사용하는 것이 좋을까?
최단 경로를 찾을 때: BFS는 시작 노드로부터 가까운 노드부터 차례대로 탐색하기 때문에 최단 경로를 찾는 문제에 적합하다.
예를 들어, 미로의 최단 경로를 찾거나, 소셜 네트워크에서의 최단 연결 경로 등을 찾을 때 사용된다.
트리의 레벨(Level)별로 정보를 탐색할 때: 트리의 레벨별 노드를 방문하거나, 트리의 최소 높이를 찾는 문제에 효과적이다.
코드
// bfs, q사용, 인접행렬, i 정점부터 시작한다.
public static void bfs(int i) {
Queue<Integer> q = new LinkedList<>();
q.offer(i);
visit[i] = true; // 노드 중복 접근 방지를 위한 방문 체크 배열.(boolean)
while (!q.isEmpty()) {
int temp = q.poll();
System.out.print(temp + " ");
for (int j = 1; j < n + 1; j++) {
if (map[temp][j] == 1 && visit[j] == false) {
q.offer(j);
visit[j] = true;
}
}
}
}
참고 및 출처
https://nolja98.tistory.com/58
https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
