2023. 3. 7. 18:46ㆍ알고리즘/개념
DFS ( Depth First Search ) 깊이 우선 탐색 / BFS( Breadth First Search ) 너비 우선 탐색
DFS와 BFS는 그래프의 전체를 탐색하는 완전 탐색 알고리즘의 기법 중 하나입니다.
아래에 애니메이션이 있습니다.
그림을 보시면 이해하기 수월하실 것입니다.
왼쪽의 그림은 DFS이고 오른쪽이 BFS 입니다.
먼저 DFS는 맨 위 정점부터 끝에 도달하면 돌아가 분기의 처음으로 돌아가 넘어가는걸 보실 수 있습니다.
이처럼 DFS는 가장 끝까지 가보고 그 다음 경우의 끝까지 계속해서 확인하며 가는 경우입니다.
오른쪽의 BFS는 갈 수 있는 분기를 하나씩 처리하며 가는 경우입니다.
a가 b, c 로 갈 수 있고 b는 d,e c는 f,g 로 방문 처리를 하며 끝까지 갈 수 있습니다.
언제, 어떻게 사용해야 할까요??
아래에 문제가 있습니다.
1. 타겟 넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165
2. 피로도
https://school.programmers.co.kr/learn/courses/30/lessons/87946
3. 소수 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/42839
4. 전력망 둘로 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/86971
5. 미로 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/159993
저는 위에 문제들을 dfs와 bfs를 이용하여 풀었습니다.
이 밖에 아주 다양한 문제를 dfs와 bfs 로 풀 수 있습니다.
DFS와 BFS 어떻게 구현하나요?
DFS
DFS는 재귀와 반복문을 이용해 방문처리를 하며 끝까지 갔다 오는 방식입니다.
스택의 원리와 재귀함수의 개념을 이용하여 구현 가능하고
시작 노드부터 하나씩 들어가며 방문처리하고
인접노드 중 방문하지 않은 인접노드를 스택에 들어가고
인접노드가 없다면 하나씩 빠지면서 뒤로 돌아갑니다.
BFS
BFS는 보통 Queue와 반복문을 통해 방문처리를하며 확인을 합니다.
큐에 맨 처음 원소를 하나씩 빼며 처리합니다.
위의 코드가 정확하게 무조건 맞는 코드는 아닙니다.
DFS와 BFS에서의 핵심은
깊게 먼저 가서 확인하냐
확인하면서 가냐의 차이입니다.
응용하는 방법은 문제에 맞게 무궁무진하므로 핵심을 생각하고 문제를 풀면 다양한 코드를 만들어 해결하실 수 있습니다.
아래 백준 기본 문제가 있습니다.
먼저 익숙해지고 그 다음 천천히 가시면 여러 문제들에 적용하실 수 있을 거라 생각합니다.
https://www.acmicpc.net/problem/1260
'알고리즘 > 개념' 카테고리의 다른 글
BackTracking 백트래킹 설명 및 문제 예시 (0) | 2023.03.14 |
---|---|
다익스트라(Dijkstra) 알고리즘 - Kotlin (0) | 2023.03.07 |
이분탐색 파라매트릭 서치 알고리즘 ( Kotlin ) (0) | 2023.03.07 |
플로이드 와샬 ( Floyd Warshall ) 알고리즘 - (Kotlin) (0) | 2023.03.05 |
크루스칼 알고리즘 & Union Find 알고리즘 ( 최소 신장 트리 , Kotlin ) (0) | 2023.03.02 |