DFS & BFS ( Kotlin )

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

2. 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

3. 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

4. 전력망 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

5. 미로 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/159993

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

저는 위에 문제들을 dfs와 bfs를 이용하여 풀었습니다.

이 밖에 아주 다양한 문제를 dfs와 bfs 로 풀 수 있습니다.

 

DFS와 BFS 어떻게 구현하나요?

 

DFS

 

DFS는 재귀와 반복문을 이용해 방문처리를 하며 끝까지 갔다 오는 방식입니다.

스택의 원리와 재귀함수의 개념을 이용하여 구현 가능하고 

시작 노드부터 하나씩 들어가며 방문처리하고

인접노드 중 방문하지 않은 인접노드를 스택에 들어가고

인접노드가 없다면 하나씩 빠지면서 뒤로 돌아갑니다.

 

BFS

BFS는 보통 Queue와 반복문을 통해 방문처리를하며 확인을 합니다.

큐에 맨 처음 원소를 하나씩 빼며 처리합니다.

 

위의 코드가 정확하게 무조건 맞는 코드는 아닙니다.

DFS와 BFS에서의 핵심은

깊게 먼저 가서 확인하냐

확인하면서 가냐의 차이입니다.

 

응용하는 방법은 문제에 맞게 무궁무진하므로 핵심을 생각하고 문제를 풀면 다양한 코드를 만들어 해결하실 수 있습니다.

 

아래 백준 기본 문제가 있습니다. 

먼저 익숙해지고 그 다음 천천히 가시면 여러 문제들에 적용하실 수 있을 거라 생각합니다.

 

https://www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net