[Algorithm] DFS (Depth-first Search)를 Java로 구현해보자!

---

안녕하세요 Coding-Knowjam입니다.

오늘은 그래프와 트리를 탐색할 때 사용되는 DFS알고리즘에 대해서 알아보겠습니다.

 

1. DFS (Depth-first Search)란?

DFS는 번역하면 깊이 우선 탐색이라고 합니다.

이름에서도 알 수 있듯이 연결된 노드를 따라서 계속 방문을 한 후에 더 이상 연결된 노드들을 없을 때 그 전 노드로 되돌아가고 다시 연결된 노드를 따라서 탐색을 합니다.

사실 글로 설명하기는 좀 애매해서 그림과 같이 설명을 드리겠습니다.

그래프 예시

위와 같은 그래프가 존재한다고 하고, 1번 노드부터 DFS탐색을 시작해보겠습니다.

• 1번 노드 방문처리 후 출력 (탐색 순서 : 1)
• 1번 노드에 인접한 노드 2번, 3번, 8번 중 하나를 방문해야 하는데 오름차순으로 방문하기로 가정하겠습니다.
• 2번 노드 방문처리 후 출력 (탐색 순서 : 1 -> 2)
• 2번 노드에 인접한 노드 6번, 8번 중 오름차순 기준이니까 6번 노드로 가겠습니다.
• 6번 노드 방문처리 후 출력 (탐색 순서 : 1 -> 2 -> 6)
• 6번 노드에 인접한 노드는 2번 노드뿐인데 이미 방문을 하였으므로 더 이상 방문처리는 하지 않고 6번 노드를 호출한 노드(부모 노드)로 다시 돌아갑니다. (여기서는 2번 노드가 됩니다)
• 2번 노드에 인접한 노드 중 8번 노드가 남아있으므로 8번 노드로 이동합니다.
• 8번 노드 방문처리 후 출력 (탐색 순서 : 1 -> 2 -> 6 -> 8)
• 8번 노드에 인접한 노드는 1번과 2번 노드인데 둘 다 모두 방문처리가 되어있으므로 더 이상 방문은 하지 않고 8번을 호출한 노드(부모 노드)인 2번 노드로 돌아갑니다.
• 2번 노드에 인접한 노드(자식 노드) 6번, 8번이 모두 방문 처리된 상태이므로 2번을 호출한 노드(부모 노드)인 1번 노드로 돌아갑니다.
• 이제 1번 노드에 인접한 노드 중 방문하지 않은 노드 3번으로 이동합니다.
• 3번 노드 방문처리 후 출력 (탐색 순서 : 1 -> 2 -> 6 -> 8 -> 3)
• 3번 노드에 연결된 노드는 5번 노드뿐이므로 5번 노드 방문 처리 후 출력 (탐색 순서 : 1 -> 2 -> 6 -> 8 -> 3 -> 5)
• 5번 노드에 연결된 노드 4번, 7번 중 오름차순 기준이니까 4번 먼저 방문처리 후 출력 
• 마지막으로 남은 7번 노드 방문 처리 후 출력하면 더 이상 방문할 노드가 없으므로 종료됩니다.

이렇게 되면 최종적으로 탐색한 순서는 다음과 같습니다.

탐색 순서(재귀) : 1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> 7

저는 오름차순 기준으로 해서 위와 같은 탐색 순서가 나왔지만, 기준이나 구현 방법에 따라서 탐색 순서는 바뀔 수 있습니다.

DFS를 코드로 구현하는 방법은 재귀로 구현하는 방법과 Stack자료구조를 사용해서 구현하는 방법 2가지가 있습니다.

위의 설명 예시는 재귀 형태로 구현했을 때의 탐색 순서입니다.

만약에 Stack자료구조로 구현을 한다면 연결된 자식 노드를 오름차순으로 Stack에 집어넣고 하나씩 꺼내서 다시 연결된 노드를 찾아서 Stack에 넣는 식으로 구현을 할 수 있습니다.

이러한 형태로 탐색은 진행하면 순서는 다음과 같습니다.

탐색 순서(Stack자료구조) : 1 -> 8 -> 3 -> 5 -> 7 -> 4 -> 2 -> 6

실제 코드로 구현해보면 스택 자료구조를 사용한 것보다는 재귀로 구현하는 게 코드가 더 짧고 간결하기 때문에 일반적으로 재귀로 많이 구현을 합니다.

그럼 코드로 구현해보겠습니다.

 

2. Java 코드로 구현

2.1 재귀(Recursion) 형태로 구현

package study.blog.codingnojam;

public class Study_DFS_Recursion {

	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void main(String[] args) {
		dfs(1);
	}
	
	static void dfs(int nodeIndex) {
		// 방문 처리
		vistied[nodeIndex] = true;
		
		// 방문 노드 출력
		System.out.print(nodeIndex + " -> ");
		
		// 방문한 노드에 인접한 노드 찾기
		for (int node : graph[nodeIndex]) {
			// 인접한 노드가 방문한 적이 없다면 DFS 수행
			if(!vistied[node]) {
				dfs(node);
			}
		}
	}
}

 

재귀로 코드를 구현하면 위의 소스코드처럼 간단하게 구현할 수 있습니다.

설명은 주석에 적어놓았으니 코드를 이해하시는데 어렵지는 않을 겁니다.

출력하면 결과는 위에서 살펴본 예시와 동일한 걸 확인하실 수 있습니다.

 

2.2 Stack 자료구조 사용해서 구현

package study.blog.codingnojam;

import java.util.Stack;

public class Study_DFS_stack {

	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	// DFS 사용 할 스택
	static Stack<Integer> stack = new Stack<>();
	
	public static void main(String[] args) {
		
		// 시작 노드를 스택에 넣어줍니다.
		stack.push(1);
		// 시작 노드 방문처리
		vistied[1] = true;
		
		// 스택이 비어있지 않으면 계속 반복
		while(!stack.isEmpty()) {
			
			// 스택에서 하나를 꺼냅니다.
			int nodeIndex = stack.pop();
			
			// 방문 노드 출력
			System.out.print(nodeIndex + " -> ");
			
			// 꺼낸 노드와 인접한 노드 찾기
			for (int LinkedNode : graph[nodeIndex]) {
				// 인접한 노드를 방문하지 않았을 경우에 스택에 넣고 방문처리 
				if(!vistied[LinkedNode]) {
					stack.push(LinkedNode);
					vistied[LinkedNode] = true;
				}
			}
		}
	}
}

 

스택으로 구현하는 것도 크게 어렵지는 않지만, 재귀가 더 짧고 간결하게 코드를 짤 수 있습니다.

스택으로 구현한 코드도 주석으로 설명을 달아드렸으니 이해하시는데 어렵지 않을 거라 생각합니다.

출력하면 결과는 위에서 살펴본 예시와 동일한 걸 확인하실 수 있습니다.

 

사실 이런 예제는 정말 단순하게 탐색하는 순서만 출력을 한 것이기 때문에 실제로 코딩 테스트와 같은 문제풀이에서는 이보다는 조금 더 응용을 해서 코드를 짜야합니다.

다음에는 실제 문제풀이를 통해서 어떻게 DFS가 사용되는지 포스팅하도록 하겠습니다.

감사합니다.

---