[자료구조] DFS(Depth First Search) Java 구현

DFS는 

Depth First Search 로 번역을 하면 깊이우선 탐색이다.

 

깊이 우선 탐색은 아래와 같은 방식으로 작동한다. 

 

해당 노드와 인접한 노드들을 방문하고 그 노드의 자식(인접노드)이 있다면 방문 다하고 난 다음에

형제 노드를 방문하는것이다. 

 

 

그렇다면 DFS의 장점과 단점에 대해서 알아보자.

 

DFS 장점

1. 현재 경로상의 노드들만 기억하면 되서 저장공간의 수요가 적다.

2. 목표 노드가 깊은 단계에 있는 경우라면 해를 빨리 구할수 있다.

3. 구현이 너비 우선 탐색보다는 쉽다.

 

DFS 단점

1. 단순 검색 속도가 BFS보다 느림

2. 해가 없는 경우에 무한 루프에 빠질수가 있다.

3. 깊이우선은 해를 구하면 종료가 되기 때문에 최단경로가 된다는 보장이 없음

 

 

그렇다면 DFS는 어떤 상황일때 주로 쓰일까?

 

자동미로를 생성하게될때나 트래버스에 주로 쓰인다고 한다.

 

자동미로를 생성할때는 랜덤으로 미로를 생성하다가 미로를 탈출하는 경로를 만들게 되면

거기서 작동이 끝나버리기 때문에 미로의 탈출 경로가 하나만 생기게돼 해당 경우에 자주 쓰이고 

 

그리고 트래버스 즉 트리 순회할때도 해당 DFS를 사용한다고 한다.

 

그럼 이제 DFS를 구현해보자.

 

나는 아래와 같은 그래프를 DFS로 구현해봤다.

 

나는 위 그래프를 인접리스트와 인접행렬을 통해서 DFS를 구현해봤다.

 

인접리스트와 인접행렬과 관련된건 아래 링크를 확인해보시면 된다.

 

https://wpioneer.tistory.com/128

[자료구조] 인접리스트 구현 : LinkedList (Java)

https://wpioneer.tistory.com/129

[자료구조] 인접행렬로 구현한 그래프 (Java)

 

 

일단 소스부터 보자.

 

Main 함수

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		
		int n = 9;
		
		AdjacencyList aj = new AdjacencyList(n);
		
		aj.addEdge(0, 1);
		aj.addEdge(1, 2);
		aj.addEdge(1, 3);
		aj.addEdge(2, 3);
		aj.addEdge(2, 4);
		aj.addEdge(3, 4);
		aj.addEdge(3, 5);
		aj.addEdge(5, 6);
		aj.addEdge(5, 7);
		aj.addEdge(6, 8);
		

		
		LinkedList<Integer>[] ll = aj.getAdj();
		
		Dfs dfs = new Dfs();
		
		
		int[] visit1 = new int[n];
		
		System.out.print("인접리스트로 구현 : ");
		dfs.dfsRoute1(3, visit1, ll); //인접 리스트로 DFS 구현
		
		System.out.println("\n--------------------------------");
		
		AdjMatrix am = new AdjMatrix(n);
		
		am.addEdge(0, 1);
		am.addEdge(1, 2);
		am.addEdge(1, 3);
		am.addEdge(2, 4);
		am.addEdge(2, 3);
		am.addEdge(3, 4);
		am.addEdge(3, 5);
		am.addEdge(5, 6);
		am.addEdge(5, 7);
		am.addEdge(6, 8);
		
		int[][] graph = am.getAdjGraph();
		int[] visit2 = new int[n];
		System.out.print("인접행렬로 구현 : ");
		dfs.dfsRoute2(3, visit2, graph);
	}

Dfs Class

package co.kr.wook;

import java.util.Iterator;
import java.util.LinkedList;

public class Dfs {

	//여기서 해야할것은 아래와 같다.
	//자식이 있다면 자식을 방문하고 자식을 다 방문했다면 다른 자식을 방문하는것이다.
	//나는 이것을 재귀호출로 구현을해서 자식이 없는애까지 방문하는걸로 구현해보려고 한다.
	
	public Dfs() {}
	
	//이번 함수에서는 root를 입력받으면 해당을 시작기점으로 하여서 자식이 없는애까지 받으려고 한다.
	public void dfsRoute1(int root, int[] visit, LinkedList<Integer>[] list) {
		//일단 root의 인접리스트를 한번 출력하는걸 만들어보자.
		
		visit[root] = 1; //해당 노드 방문 처리
		System.out.print(root + " ");
		LinkedList<Integer> rootNode = list[root]; //해당 노드와 인접한노드 리스트를 받아옴
		
		Iterator it = rootNode.iterator();
		
		while(it.hasNext()) { //해당 노드와 인접한 노드에 접근
			int node = (int) it.next();
			if(visit[node]!=1) //인접노드가 방문되지 않았다면 방문처리
				dfsRoute1(node,visit,list);
		}
	}
	
	public void dfsRoute2(int root, int[] visit, int[][] adjM) {
		
		visit[root] = 1; //해당 노드 방문 처리
		System.out.print(root+" ");
		for(int i = 0; i<adjM[root].length;i++) {
			if(adjM[root][i] == 1 && visit[i] == 0) {//간선이고 해당 노드 방문 안했을때 
				dfsRoute2(i,visit,adjM);
			}
		}
	}
}

 

 

방문 처리를 하고 방문 되어있는 노드들은 건너뛰고 방문이 안되어 있는것들은 

재귀 호출을 하여서 방문 처리하게 하였다.

 

내가 만든 그래프의 결과는 아래와 같다.

 

시작노드가 0일때 경로 결과

 

인접리스트로 구현 : 0 1 2 3 4 5 6 8 7 
--------------------------------
인접행렬로 구현 : 0 1 2 3 4 5 6 8 7 

 

시작노드가 3일때 경로 결과

 

인접리스트로 구현 : 3 1 0 2 4 5 6 8 7 
--------------------------------
인접행렬로 구현 : 3 1 0 2 4 5 6 8 7