DFS & BFS ( Kotlin )

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

1260번: DFS와 BFS