[도구정리] DFS, BFS
DFS(깊이 우선 탐색) and BFS(너비 우선 탐색)
두 가지 모두 조건에 부합하는 정답을 찾기 위해 탐색을 실행하는 알고리즘이다.
BFS는 너비 우선 탐색을 진행한다. 위의 그림을 보면 루트 노드에서 시작해서 인접한 노드 순으로 방문하며 탐색을 진행하는 것이다. 따라서 루트 노드인 A에서 시작하여 그다음 인접 노드 B, C, D를 탐색한 후 그것의 인접 노드인 E, F 순으로 탐색을 마친다.
-> 주로 두 노드 사이의 최단 거리 탐색에 많이 사용된다.
DFS는 깊이 우선 탐색을 진행한다. 그림에서 알 수 있듯, A를 탐색하면 그 다음 노드인 BCD 중 하나를 탐색 후 그 분기에 대한 완전 탐색을 마친 뒤에야 다음 분기로 진행하는 것이다.
->예를 들면, 미로를 따라가다가 길이 막히면 다시 돌아와서 탐색을 진행하는 방식과 유사하다.
가장 대표적인 문제를 통해 코드를 분석해보자.
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
풀이
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static boolean[] check;
static int[][] arr;
static int node, line, start;
static Queue<Integer> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
node = Integer.parseInt(st.nextToken());
line = Integer.parseInt(st.nextToken());
start= Integer.parseInt(st.nextToken());
arr = new int[node+1][node+1];
check = new boolean[node+1];
for(int i = 0 ; i < line ; i ++) {
StringTokenizer str = new StringTokenizer(br.readLine());
int a = Integer.parseInt(str.nextToken());
int b = Integer.parseInt(str.nextToken());
arr[a][b] = arr[b][a] = 1;
}
dfs(start);
sb.append("\n");
check = new boolean[node+1];
bfs(start);
System.out.println(sb);
}
public static void dfs(int start) {
check[start] = true;
sb.append(start + " ");
for(int i = 0 ; i <= node ; i++) {
if(arr[start][i] == 1 && !check[i])
dfs(i);
}
}
public static void bfs(int start) {
q.add(start);
check[start] = true;
while(!q.isEmpty()) {
start = q.poll();
sb.append(start + " ");
for(int i = 1 ; i <= node ; i++) {
if(arr[start][i] == 1 && !check[i]) {
q.add(i);
check[i] = true;
}
}
}
}
}
먼저 클래스 전체에서 쓰기 위한 배열과 변수들을 선언해 준다. 또한 bfs에서 큐를 사용하기 때문에 큐 역시 선언해준다.
이후 사용자 입력에 따른 간선의 정보를 배열에 저장하게 된다.
여기서 아래와 같이 대입하는 이유는 간선이라는 것은 방향을 띄고 있지 않기 때문에 a->b가 있으면 b->a라는 것을 표현하기 위해서이다.
arr[a][b] = arr[b][a] = 1;
이제 본격적으로 dfs와 bfs에 대해 알아보자.
먼저 dfs이다.
public static void dfs(int start) {
check[start] = true;
sb.append(start + " ");
for(int i = 0 ; i <= node ; i++) {
if(arr[start][i] == 1 && !check[i])
dfs(i);
}
}1. 매개변수로 시작지점(시작노드)을 받아온다.
2. check배열(탐색 완료했는지)을 true로 변경하여 탐색 완료를 표시한 후, 스트링빌더를 통해 정보를 저장한다.
3. for문을 통해 다른 노드들에 대한 탐색을 진행하게 된다.
4. [start][i]로 이루어진 곳 중에 노드가 연결된 것인지(==1을 통한 검사) and 방문하지 않았던 노드인지에 대한 검사를 한 후, 이 지점에 대해서 재귀적으로 dfs를 선언한다.
여기서 재귀적이라는 것이 의문일 수 있는데, 하나의 노드로 진입하여 그 노드에서 분기한 것이 있다면 모두 탐색을 마치고 다시 위로 돌아간다고 생각하면 된다.(깊이 우선 탐색이라는 것을 잊지 말자!)
이 그림에서 다시 알아보자. 먼저 왼쪽 분기에 대한 탐색을 진행한 후 5-6-7로 이루어진 탐색 후에 다시 5의 오른쪽 분기인 -8에 대한 탐색을 진행하기 위해 재귀적으로 진행된다.
코드에 대한 순서를 보면 dfs(5)가 들어오게 되고 6,7 이진행 된 후에 다시 5에 대한 for문에서 arr [5][8]이 진행된다고 생각하면 된다.
다음으로 bfs이다.
public static void bfs(int start) {
q.add(start);
check[start] = true;
while(!q.isEmpty()) {
start = q.poll();
sb.append(start + " ");
for(int i = 1 ; i <= node ; i++) {
if(arr[start][i] == 1 && !check[i]) {
q.add(i);
check[i] = true;
}
}
}
}
1. 먼저 큐에 시작 노드를 넣고, 방문했음을 체크한다.
2. 이후 큐가 비어있지 않을 때까지 while문을 통해 탐색을 하게 된다.
2-1. 큐(선입선출)를 꺼내 시작 노드를 지정한다. 이 후 시작 노드의 다음 깊이에서 방문 가능한 모든 노드를 확인하여 큐에 집어넣음과 동시에 방문했음을 체크한다.
3. 다음 큐에 대해 마찬가지로 탐색을 진행하게 된다.
여기서 보면 1번이 먼저 큐에 들어간다.
-> 그다음 와일문을 진행하며 2, 3, 4를 큐에 집어넣고 방문 체크를 한다.
-> 2번이 큐의 제일 앞부분에 위치하기 때문에 poll()을 통해 start가 되고 2와 간선으로 연결되었으면서 방문한 적이 없는 5가 큐에 들어간다. 더 이상 들어갈 것이 없기 때문에 while문 조건 검사로 되돌아간다.
-> 큐가 비어있지 않기 때문에 다음 큐인 3이 나온다. 이때 6,7이 큐에 들어가게 된다.
-> 마찬가지로 4... 가 진행되며 탐색을 마치게 된다.
DFS, BFS는 코딩 테스트에서 가장 많이, 필수적으로 출제되는 문제 중 하나이다. 따라서 기본 코드 및 응용을 통한 다양한 표현법 역시 이해하고 숙지해야 할 것 같다.