[DFS] DFS의 설명과 간단한 예제풀이

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

1. 특징

1. 자기 자식을 호출하는 순환 알고리즘의 형태를 지닌다. (재귀 or 스택)

2. 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다. (이것을 검사하지 않으면 무한루프에 빠지게 된다. ex) visited[idx] = true;)

3. 우리가 미로의 길을 계속 가다가 더 이상 갈 수 없게 되면 우리는 가장 가까운 갈림길(새로운 분기)로 돌아와서 다른 방향으로 탐색을 진행하는 것과 비슷한 양식이다.

4. 모든 노드를 방문하려고 할때 이 방식을 사용한다.

5. BFS(너비 우선 탐색)보다 더 간단하다.

6. 검색 속도 자체는 BFS(너비 우선 탐색)에 비해서 느리다.

 

DFS를 Java코드로 구현해보자

2-1 재귀(Recusion)을 사용한 구현방법

import java.util.Scanner;

public class Main {
	
	static final int MAX_N = 10;
	static int N, E;
	
	static boolean[] visited = new boolean[MAX_N]; //여기서 visitied배열의 크기는 노드의 개수+1
	
	static int[][] graph = new int[MAX_N][MAX_N];
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		E = sc.nextInt();
		
		for(int i=0; i<N; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			
			graph[u][v] = graph[v][u] = 1;
		}
		dfs(0);
	}
	
	public static void dfs(int nodeIdx) {
		
		visited[nodeIdx] = true;
		
		System.out.print(nodeIdx + " 다음 노드는 ");
		
		//방문한 노드에 인접한 노드를 찾기
		for(int next=0; next<N; next++) {
			if(!visited[next] && graph[nodeIdx][next] != 0) {
				dfs(next);
			}
		}
		
	}
}

 

---

2-2 Stack 자료구조를 사용한 구현방법

import java.util.Scanner;
import java.util.Stack;

public class Main {

	static final int MAX_N = 10;
	static int N, E;

	static int[][] graph = new int[MAX_N][MAX_N];

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		E = sc.nextInt();

		for (int i = 0; i < N; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();

			graph[u][v] = graph[v][u] = 1;
		}
		dfs(0);
	}

	public static void dfs(int nodeIdx) {
		boolean[] visited = new boolean[MAX_N];
		Stack<Integer> stack = new Stack<>();
		
		stack.push(nodeIdx);

		while(!stack.isEmpty()) {
			int curr = stack.pop();
			
			if(visited[curr]) continue;
			
			visited[curr] = true;
			System.out.println(curr + "다음 노드는 ");
			
			for(int next=0; next<N; next++) {
				if(!visited[next] && graph[curr][next] != 0) {
					stack.push(next);
				}
			}
			
		}
	
	}
}