DFS와 BFS
알고리즘 문제를 본격적으로 풀고 코딩테스트를 준비하기 전에, 가장 내가 약하다고 생각하는 그래프 탐색 알고리즘 개념을 한 번 정리하려고 한다. 컴알 수업을 듣긴 했지만 당시에 너무 대충 공부해서 기억이 하나도 안난다. 우선 두 알고리즘의 기본 틀과 탐색 방식을 살펴보고 비교해보자.
DFS
DFS는 Depth-First Search, 즉 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
탐색 순서
위와 같은 예시의 그래프가 주어지고, 1부터 노드 탐색을 시작할 때 DFS를 이용한 탐색 순서는 다음과 같다.
1 → 2 → 7 → 6 → 8 → 3 → 4 → 5
구현 방식
DFS는 스택 자료구조 (혹은 재귀 함수)를 이용하여 구현한다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
- 스택 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리한다.
- 방문하지 않은 인접 노드가 하나도 없으면 스택에서 최상단 노드를 꺼낸다.
- 더 이상 2~3번의 과정을 수행할 수 없을 때까지 반복한다.
코드
이러한 기본 로직을 자바로 구현한 코드는 아래와 같다.
자료구조
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void dfs(int x) {
// ...
}
public static void initGraph() {
// ...
}
public static void main(String[] args) {
// ...
}
}우선, 그래프를 저장할 변수는 이중 중첩 ArrayList로 선언한다. 외부 ArrayList가 모든 노드를 의미하고, 각 노드에 붙은 내부 ArrayList에는 그 노드와 연결된 노드의 정보를 저장하는 것이다. 다른 자료구조를 사용해도 되지만 재귀 함수로 구현할 때 배열보다는 ArrayList가 훨씬 편리한 것 같다.
또한, 탐색 완료한 노드를 체크하기 위해 visited 배열을 선언한다. 탐색 완료할 때마다 boolean 값을 업데이트 시키고, 이를 바탕으로 그 노드가 이미 방문되었는지 아닌지 판단하는 것이다.
메소드
DFS 함수는 재귀 호출이나 스택을 사용해서 구현할 수 있으며, 재귀 호출로 구현한 예시는 아래 코드와 같다. 보통 스택보다 재귀 호출이 코드가 더 간결하고 명확해서 재귀 호출로 많이 구현하는 것 같다.
현재 노드를 방문처리하고, 현재 노드와 연결된 + 아직 방문되지 않은 노드들을 재귀적으로 방문하는 것이 포인트다.
public static void dfs(int x) {
// 현재 노드를 방문 처리
visited[x] = true;
System.out.print(x + " ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited[y]) dfs(y);
}
}그래프를 초기화하는 코드는 아래와 같다.
public static void initGraph() {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
}그리고 위 함수들을 호출하고 그래프를 탐색하는 main 함수는 아래와 같다.
public static void main(String[] args){
initGraph();
dfs(1);
}BFS
BFS는 Breadth-First Search, 즉 너비 우선 탐색으로, 노드에서 가까운 노드를 우선적으로 탐색하는 알고리즘이다.
탐색 순서
위와 같은 예시의 그래프가 주어지고, 1부터 노드 탐색을 시작할 때 BFS를 이용한 탐색 순서는 다음과 같다.
1 → 2 → 3 → 8 → 7 → 4 → 5 → 6
구현 방식
BFS는 큐 자료구조를 이용하여 구현한다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
코드
이러한 기본 로직을 자바로 구현한 코드는 아래와 같다.
자료구조
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void bfs(int start) {
// ...
}
public static void initGraph() {
// ...
}
public static void main(String[] args) {
// ...
}
}우선, 그래프를 저장할 변수는 DFS와 마찬가지로 이중 중첩 ArrayList로 선언한다.
또한, 탐색 완료한 노드를 체크하기 위해 visited 배열도 선언한다.
메소드
BFS 함수를 정의한 코드는 아래와 같다.
큐를 구현한 LinkedList를 통해 재귀적인 호출 없이 그래프를 탐색한다.
아직 방문하지 않은 연결된 노드들을 모두 한 번에 방문 처리한다는 점이 포인트다. 같은 거리에 있는, 즉 바로 연결되어 있는 인접 노드들을 우선적으로 탐색하는 것이다.
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.isEmpty()) {
// 큐에서 하나의 노드를 뽑아 출력
int x = q.poll();
System.out.print(x + " ");
// 해당 노드와 연결된, 아직 방문하지 않은 노드들을 큐에 삽입
for(int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if(!visited[y]) {
q.offer(y);
visited[y] = true;
}
}
}
}그래프를 초기화하고 그래프 탐색 메소드를 호출하는 것은 위의 DFS 코드와 동일하다.
참고
(이코테 2021 강의 몰아보기) 3. DFS & BFS
[자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java
