[알고리즘]그래프3 - DFS(feat. Java)

DFS란?

DFS란 그래프를 순회하는 알고리즘 중 하나이다. Depth-First Search의 줄임말로 깊이 우선 탐색이라고 한다.

 

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

 

예를 들어 다음 그림에서,

 

 

1번 노드에서 DFS를 사용하여 탐색을 진행한다고 한다면, (연결된 노드가 여러개라면 오름차순으로 방문한다고 가정)

• 1번 노드 방문 후 2, 3번 노드 중 2번으로 방문
• 2번 노드 방문 후 6, 8번 노드 중 6번으로 방문
• 6번 노드 방문 후 더 이상 연결된 노드가 없으므로 2번으로 돌아감
• 2번 노드에서 방문하지 않았던 8번으로 방문
• 8번 노드 방문 후 연결된 모든 노드가 방문을 한 노드이므로 2번으로 돌아감
• 2번의 모든 노드가 방문되었으므로 1번으로 돌아감
• 1번에서 방문하지 않은 3번으로 방문
• 3번 방문 후 5번으로 방문
• 5번 방문 후 4,7번 노등 중 4번으로 방문
• 4번 방문 후 7번으로 방문
• 7번 방문 후 더 이상 방문할 노드가 없으므로 4번으로 돌아감
• 4번에서 더 이상 방문할 노드가 없으므로 5번으로 돌아감
• 5번에서 더 이상 방문할 노드가 없으므로 3번으로 돌아감
• 3번에서 더 이상 방문할 노드가 없으므로 1번으로 돌아감

최종적으로 탐색 순서는, 1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> 7이 됩니다.

 

 

 

코드 구현

DFS 탐색 알고리즘은 깊이를 우선 탐색하다 보니 재귀를 이용하여 구현을 합니다. 

 

이 코드를 통해 DFS 구현에 익숙해지고 응용할 수 있게 된다면 여러 코딩 테스트 문제들도 풀 수 있습니다!!

 

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);
			}
		}
	}
}