[ 알고리즘 ] 깊이 우선 탐색 (DFS)

DFS vs BFS

 

 

 

깊이 우선 탐색이란?(Depth First Search)

"한거번에 덤비지말고 한명씩 덤벼" 

그래프의 시작노드에서 출발하고 다음 구역으로 넘어가기 전에 해당 구역을 완벽하게 탐색
일반적으로 BFS에 비해 널리 쓰인다. (코테에서 대부분의 탐색은 DFS로 구현)

 

DFS는 주로 스택을 통한 반복이나 재귀를 통한 반복 구조(가장 일반적)로 구현.

 

 

 

 

대표 유형

• 경로탐색 유형(최단거리, 시간)
• 네트워크 유형(연결) : 여러개체들이 주어진 상태에서 연결되어있는 그룹의 갯수, 두 개체가 같은 네트워크안에서 연결되어있는지 확인
• 조합 유형(모든 조합 만들기) : 여러가지의 조합을 만들고 비교해야하는 문제

 

 

 

자바 구현

public class DFS_Recursion {
	// 오름차순 
    	// 재귀
	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	// 인덱스가 각각의 노드번호가 될 수 있게 0번인덱스는 아무것도 없는 상태라고 생각하시면됩니다.
	static int[][] graph = {
                                {},          // 노드 0에 해당하는 빈 리스트
                                {2, 3, 8},   // 노드 1에 해당하는 연결된 노드 리스트
                                {1, 6, 8},   // 노드 2에 해당하는 연결된 노드 리스트
                                {1, 5},      // 노드 3에 해당하는 연결된 노드 리스트
                                {5, 7},      // 노드 4에 해당하는 연결된 노드 리스트
                                {3, 4, 7},   // 노드 5에 해당하는 연결된 노드 리스트
                                {2},         // 노드 6에 해당하는 연결된 노드 리스트
                                {4, 5},      // 노드 7에 해당하는 연결된 노드 리스트
                                {1, 2}       // 노드 8에 해당하는 연결된 노드 리스트
			};
	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);
			}
		}
	}
}





[결과]
1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> 7 ->

 

 

 

참고

https://codingnojam.tistory.com/44