DFS와 BFS란? 작동 방식과 구현 방법(with 자바)
이 글은 DFS와 BFS 개념에 대해 설명하고, 작동 방식을 그림으로 보여주며, 이러한 작동 방식을 자바 소스 코드로 구현합니다.
학습 목표
ㆍDFS
ㆍBFS
ㆍ정리
DFS
· DFS(Depth-First Search)는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
알고리즘 동작 방식
· 스택 자료구조를 이용한다.
1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고,
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
* ‘방문 처리': 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 이를 통해 각 노드를 한 번씩만 처리할 수 있다.
▶ 예시 - 그래프의 노드 1을 시작 노드로 설정하여 DFS를 이용해 탐색
인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.
방문 처리된 노드는 회색으로, 현재 처리하는 스택의 최상단 노드는 하늘색으로 표현한다.
step1. 시작 노드 ‘1’을 스택에 삽입하고 방문 처리
step2. 스택의 최상단 노드 ‘1’에 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’ 중에서 가장 작은 노드 ‘2’를 스택에 넣고 방문 처리
step3. 스택의 최상단 노드 ‘2’에 방문하지 않은 인접 노드 ‘7’을 스택에 넣고 방문 처리
step4. 스택의 최상단 노드 ‘7’에 방문하지 않은 인접 노드 ‘6’과 ‘8’ 중에서 가장 작은 노드인 ‘6’을 스택에 넣고 방문 처리
step5. 스택의 최상단 노드 ‘6’에 방문하지 않은 인접 노드가 없으므로, 스택에서 ‘6’번 노드를 꺼냄
step6. 스택의 최상단 노드 ‘7’에 방문하지 않은 인접 노드 ‘8’이 있으므로, ‘8’번 노드를 스택에 넣고 방문 처리
step7. 스택 최상단 노드 ‘8’에 방문하지 않은 인접 노드가 없으므로, 스택에서 ‘8’번 노드를 꺼냄
step8. 스택의 최상단 노드 ‘7’에 방문하지 않은 인접 노드가 없으므로, 스택에서 ‘7’번 노드를 꺼냄
step9. 스택의 최상단 노드 ‘2’에 방문하지 않은 인접 노드가 없으므로, 스택에서 ‘2’번 노드를 꺼냄
step10. 스택의 최상단 노드 ‘1’에 방문하지 않은 인접 노드 ‘3’을 스택에 넣고 방문 처리
step11. 스택의 최상단 노드 ‘3’에 방문하지 않은 인접 노드 ‘4’, ‘5’ 중 가장 작은 노드 ‘4’를 스택에 넣고 방문 처리
step12. 스택의 최상단 노드 ‘4’에 방문하지 않은 인접 노드 ‘5’가 있으므로, ‘5’번 노드를 스택에 넣고 방문 처리
step13. 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례대로 꺼내면 다음과 같다.
위 단계에서 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다.
1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5
· 깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초하므로, 실제 구현은 재귀 함수를 이용했을 때 간결하게 구현할 수 있다.
· 소요시간: 데이터의 개수가 N개인 경우, O(N)
▶ 예시 - 재귀 함수를 통해 dfs 구현
public class DFSExamRecursion {
//각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
public static boolean [] visited = {false, false, false ,false ,false ,false ,false ,false, false};
// 각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
public static int[][] graph = {{},
{2, 3, 8},
{1, 7},
{1, 4, 5},
{3, 5},
{3, 4},
{7},
{2, 6, 8},
{1, 7}};
public static void main(String[] args){
int start = 1; // 시작 노드
dfs(start);
}
/*
* dfs 알고리즘을 수행하는 함수
* @param v 탐색할 노드
*/
public static void dfs(int v){
// 현재 노드 방문 처리
visited[v] = true;
// 방문 노드 출력
System.out.print(v + "");
// 인접 노드 탐색
for (int i : graph[v]){
// 방문하지 않은 인접 노드 중 가장 작은 노드를 스택에 넣기
if (visited[i]==false){
dfs(i);
}
}
}
}
▶ 예시 - Stack 클래스를 통한 DFS 구현
public class DFS_Stack {
public static void main(String[] args){
//각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
int [][]graph = {{},
{2, 3, 8},
{1, 7},
{1, 4, 5},
{3, 5},
{3, 4},
{7},
{2, 6, 8},
{1, 7}};
//각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
boolean [] visited = {false, false, false ,false ,false ,false ,false ,false, false};
//정의된 DFS 함수 호출
DFS_Stack dfsExam = new DFS_Stack();
dfsExam.dfs(graph, 1, visited);
}
/*
* dfs 메서드
* @param graph 노드 연결 정보를 저장
* @param v 방문을 시작하는 최상단 노드의 위치
* @param visited 노드 방문 정보를 저장
*/
void dfs(int [][]graph,int start, boolean [] visited){
//시작 노드를 방문 처리
visited[start] = true;
System.out.print(start + " ");//방문 노드 출력
Deque<Integer> stack = new LinkedList<>();
stack.push(start); //시작 노드를 스택에 입력
while(!stack.isEmpty()){
int now = stack.peek();
boolean hasNearNode = false; // 방문하지 않은 인접 노드가 있는지 확인
//인접한 노드를 방문하지 않았을 경우 스택에 넣고 방문처리
for(int i: graph[now]){
if (!visited[i]) {
hasNearNode = true;
stack.push(i);
visited[i] = true;
System.out.print(i + " ");//방문 노드 출력
break;
}
}
//반문하지 않은 인접 노드가 없는 경우 해당 노드 꺼내기
if(hasNearNode==false)
stack.pop();
}
}
}
BFS
· BFS(Breadth First Search)의 약자로 ‘너비 우선 탐색’ 알고리즘을 의미한다.
- 즉, 가까운 노드부터 탐색하는 알고리즘이다.
- 최대한 멀리 있는 노드를 우선으로 탐색하는 DFS와는 반대다.
알고리즘의 동작 방식
· 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.
- 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가며, 가까운 노드부터 탐색하게 된다.
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
▶ 예시 - 그래프의 노드 1을 시작 노드로 설정하여 BFS를 이용해 탐색
· 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 큐에 삽입한다고 가정한다.
큐에 원소가 들어올 때, 위에서 들어오고 아래쪽에서 꺼낸다.
step 1. 시작 노드 ‘1’을 큐에 삽입하고 방문 처리 한다.
방문 처리된 노드는 회색으로, 큐에서 꺼내 현재 처리하는 노드는 하늘색으로 표시하다.
step 2. 큐에서 노드 ‘1’을 꺼내고 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’을 모두 큐에 삽입하고 방문 처리한다.
step 3. 큐에서 노드 ‘2’를 꺼내고 방문하지 않은 인접 노드 ‘7’을 큐에 삽입하고 방문 처리 한다.
step 4. 큐에서 노드 ‘3’을 꺼내고 방문하지 않은 인접 노드 ‘4’와 ‘5’를 모두 큐에 삽입하고 방문 처리한다.
step 5. 큐에서 노드 ‘8’을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.
step 6. 큐에서 노드 ‘7’을 꺼내고 방문하지 않은 인접 노드 ‘6’을 큐에 삽입하고 방문 처리를 한다.
step 7. 남아 있는 노드에 방문하지 않은 인접 노드가 없다. 따라서 모든 노드를 차례로 꺼낸다.
노드의 탐색 순서(큐에 들어간 순서) 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6
· 너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다.
· 구현할 때는 언어에서 제공하는 큐 라이브러리를 사용하자.
· 탐색 수행 시간은 O(N)의 시간이 소요되고, 일반적인 경우 실제 수행 시간은 DFS보다 좋다.
- 재귀 함수로 DFS를 구현하면 컴퓨터 시스템의 동작 특성상 실제 프로그램의 수행 시간이 느려질 수 있기 때문이다.
import java.util.LinkedList;
import java.util.Queue;
public class BFS {
public static void main(String[] args){
//각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
int [][]graph = {{},
{2, 3, 8},
{1, 7},
{1, 4, 5},
{3, 5},
{3, 4},
{7},
{2, 6, 8},
{1, 7}};
//각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
boolean [] visited = {false, false, false ,false ,false ,false ,false ,false, false};
int start = 1; // 시작 노드
// 큐 구현
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌때까지 반복
while(!queue.isEmpty()){
// 큐에서 하나의 원소를 뽑아 출력
int v = queue.poll();
System.out.println(v + " ");
// 인접한 노드 중 아직 방문하지 않은 원소들을 큐에 삽입
for (int i : graph[v]){
if (visited[i] == false){
queue.add(i);
visited[i] = true;
}
}
}
}
}
결과
정리
| DFS | BFS | |
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀 함수 또는 스택 자료구조 이용 | 큐 자료구조 이용 |
· 앞서 DFS와 BFS를 설명하는 데 전형적인 그래프 그림을 이용했다.
1차원 배열이나 2차원 배열 또한 그래프 형태로 생각하면 수월하게 문제를 풀 수 있다.
· 예를 들어 게임 맵이 3 x 3 형태의 2차원 배열이고 각 데이터를 좌표라고 생각해보자.
이때 각 표로 상하좌우로만 이동할 수 있다면, 모든 좌표의 형태를 다음처럼 그래프의 형태로 바꿔서 생각할 수 있다.
· 코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 이렇게 그래프 형태로 바꿔서 생각하자. 풀이 방법을 더 쉽게 떠올릴 수 있다.
'알고리즘&코딩테스트' 카테고리의 다른 글
| [Algorithm] BFS 문제 풀이 - 미로 탈출 (자바코드) (0) | 2021.02.02 |
|---|---|
| [Algorithm] DFS 문제 풀이 - 음료수얼려먹기 (자바코드) (0) | 2021.02.01 |
| [Algorithm] DFS와 BFS를 이해하기 위한 기본 지식들 - 탐색, 스택(Stack)과 큐(Stack), 재귀 함수, 그래프(Graph) (0) | 2021.01.24 |
| 알고리즘 구현 유형 문제 풀이 - 왕실의 나이트 (0) | 2021.01.17 |
| [Algorithm] 알고리즘 구현 유형 문제 풀이 - 시각 문제 (0) | 2021.01.16 |
댓글