[알고리즘] BFS와 DFS

그래프 탐색

 

그리프란 정점과 간선으로 이루어진 자료구조의 일종이다.

 

그리고 그래프에서의 탐색은 하나의 정점, 즉 시작점에서 출발하여 차례대로 정점을 방문하여 목표 정점을 방문하는 것을 말한다.

예를 들자면 그래프 내 어떤 노드와 다른 특정 노드가 연결되어 있는지를 검사하는 것, 혹은 사람간의 관계가 이어져있는지 검사하는 것이 바로 그래프 탐색이다.

 

BFS와 DFS는 모두 이러한 그래프 탐색 알고리즘의 일종이다.

 

 

 

BFS (너비 우선 탐색, Breadth-First Search)

 

BFS는 쉽게 말해, 인접한 노드들을 전부 방문한 후 다음 노드로 이동하는 방법이다.

 

아래와 같은 그래프가 있다고 가정하자.

BFS를 위해 다음 두 개의 조건을 설정하자.

• 시작 노드는 1이다.
• 다음 노드로 향할 때 숫자가 작은 노드에 먼저 접근한다.

 

앞서 언급한 BFS는 자신과 이어진 모든 노드를 탐색하게 된다.

그렇기에 1부터 시작하면 1과 연결된, 작은 노드인 2부터 연결된다.

1

2

3

그리고 다음은 1 다음에 채워진 2로 넘어가여 같은 작업을 반복한다.

1

2

3

4

5

다음은 3으로 넘어가게 되는데, 3은 1, 2, 5와 연결되어 있지만 모든 노드들이 전부 스택 안에 있으니 건너뛰어진다.

그리고 4로 들어가 4와 연결된 6이 마지막으로 채워지게 된다.

1

2

3

4

5

6

 

BFS는 최단 경로를 찾을 때 주로 사용하게 된다.

 

 

 

DFS (깊이 우선 탐색, Depth-First Search)

 

BFS가 인접한 노드들을 전부 탐색하며 진행했다면, DFS는 노드들의 연결을 따라 끝까지 가는 방식이라 볼 수 있다.

 

위의 그래프를 다시 한 번 보자.

마찬가지로 1부터 시작하여 작은 수부터 먼저 진행한다.

 

앞서 언급했든 DFS는 시작점부터 시작하여 노드의 연결을 따라 끝까지 진행된다.

1부터 시작되었기에, 작은 수인 2 방향을 시작으로 진행된다.

1

2

4

6

6에서 더 이상 나아갈 노드가 없으므로, 다시 돌아와 중간 지점인 2에서 5로 다시 한 번 연결된다.

1

2

4

6

5

3

 

 

 

BFS와 DFS

 

만약 그래프의 모든 정점을 방문해야 하는 문제를 풀어야 한다면 어떤 알고리즘을 사용해도 문제는 없다.

 

 

하지만 최단 경로, 최단 거리를 구하는 알고리즘 문제를 풀 경우 BFS를 사용하는 것이 효과적이다.

두 알고리즘 모두 효율성을 위해 목표 정점에 도달 시 탐색을 멈추기 때문에 일어나는 현상인데,

예시를 들기 위해 아래의 경우를 생각해보자.

1에서 시작하여 7까지의 거리를 계산하는 문제가 있을 때, 눈으로 봤을 때의 정답은 1 => 3 => 7 으로 2이다.

DFS를 사용할 경우의 노드간 연결은 다음과 같이 출력된다.

1	2	4	6	5	7	3
0	1	2	3	2	3	1

여기서 아래의 숫자는 길이이다.

이렇게 되었을 때, 어쩔 수 없이 DFS는 1 => 2 => 5 => 7 의 거리를 정답으로 인식하고 출력하게된다.

 

다음은 이 문제를 BFS로 풀었을 때이다.

1	2	3	4	5	7	6
0	1	1	2	2	2	3

BFS는 특성상 시작 노드로부터 가까운 노드들을 우선으로 탐색하기 때문에 먼저 찾아지는 해답이 최단 거리가 된다.

 

 

 

 

코드

위의 그래프를 입력으로, 전체를 탐색하는 BFS, DFS 알고리즘의 코드는 아래와 같다.

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class main{
	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);

		int n = s.nextInt(); // 정점의 갯수
		int m = s.nextInt(); // 간선의 갯수
		int v = s.nextInt(); // 출발점

		int[][] graph = new int[n + 1][n + 1]; // 그래프 구성

		for (int i = 0; i < m; i++) {
			int startNode = s.nextInt();
			int endNode = s.nextInt();

			graph[startNode][endNode] = 1;
			graph[endNode][startNode] = 1;
		}

		Boolean[] isVisited = new Boolean[n + 1]; // 방문 여부 확인
		Arrays.fill(isVisited, false); // false로 초기화

		DFS(n, v, graph, isVisited); // 노드 수, 시작점, 그래프, 방문여부
		System.out.println();

		Arrays.fill(isVisited, false); // 다시 초기화
		BFS(n, v, graph, isVisited); // 노드 수, 시작점, 그래프, 방문여부

	}

	public static void BFS(int n, int node, int[][] graph, Boolean[] isVisited) {
		// 순서대로 진행하기 위해 순서 저장
		Queue<Integer> queue = new LinkedList<>();
		// 첫 시작 노드 기록
		queue.offer(node);
		isVisited[node] = true;

		while (!queue.isEmpty()) {
			int tmp = queue.poll(); // 현재 위치 값 빼오기
			System.out.print(tmp + " ");

			for (int i = 1; i < n + 1; i++) {
				if (graph[i][tmp] == 1 && !isVisited[i]) {
					// 경로가 있고 방문한 적이 없으면 진행
					queue.offer(i);
					isVisited[i] = true;
				}
			}
		}
	}

	public static void DFS(int n, int node, int[][] graph, Boolean[] isVisited) {
		// 방문한 사실 기록
		isVisited[node] = true;
		System.out.print(node + " ");

		for (int i = 1; i < n + 1; i++) {
			if (graph[i][node] == 1 && !isVisited[i]) {
				// 경로가 있고 방문한 적이 없으면 진행
				DFS(n, i, graph, isVisited);
			}
		}
	}
}