DFS 알고리즘 공부

BFS에 이어  DFS도 같이 공부했다.

재귀 쪽은 실무에서 많이 사용하진 않아서 엄~청 익숙한 방법은 아니지만? 구현하는게 어렵진 않았다.

애초에 BFS보다는 DFS가 개념이 쉽다. DFS를 먼저하고 BFS 보니 잠깐 띠용 했었음.

+ DFS는 재귀로 구현하는게 쉬운듯하다. 혹시 모르니 Stack을 사용해서도 구현해봐야겠다.

 

---

 

DFS(깊이 우선 탐색)

1. BFS와 같이 그래프 이론이자 완전탐색 방법 중 하나이다.
2. 깊이 우선 탐색으로 노드 하나를 정하고 연결되어 있는 노드가 없을 때까지 깊이 탐색한 후 다음 노드로 넘어간다.
   • 시작 노드와 연결 된 노드들을 찾은 후, 그중 하나를 골라 연결된 노드가 없을때까지 그 줄기를 탐색한다.
   • BFS가 가로로 쭉 쭉 탐색하는 느낌이였다면, DFS는 세로로 쭉 쭉 탐색한다.
3. Stack과 구조를 사용하는 방식.

* 이론 공부는 youtu.be/CJiF-muKz30 을 참고했다. 설명을 쉽게 잘 해주신다.

 

 

---

메인 함수

		int[][] graph = {
				{},
				{2, 3, 8},
				{1, 7}, 
				{1, 4, 5},
				{3, 5},
				{3, 4},
				{7}, 
				{2,6,8}, 
				{1, 7}
		};
		
		boolean[] visited = new boolean[graph.length]; 
		
		// 1. 재귀함수 방식 DFS
		DFS(graph, visited, 1);

DFS 재귀 함수

	// graph : 그래프  정보를 담고 있는 배열
	// visited : 방문 정보를 담고 있는 배열로 그래프의 노드 수와 동일
	// num : 방문하려는 노드의 번호
	public static void DFS(int[][] graph, boolean[] visited, int num) {
		if(visited[num] == true)		// 이미 들렸으면 back
			return;
		
		visited[num] = true;		// 1번 노드 들렸음
		System.out.println(num);
		
		if(graph[num].length > 0) {
			for(int i=0 ; i<graph[num].length ; i++) {
				DFS(graph, visited, graph[num][i]);				
			}
		}
	}