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

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

"루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법"

 

 

넓이 우선 탐색과

(Breadth-first Search)

대비되는 알고리즘으로

 

말 그대로 넓이 보단

깊이를 우선적으로

탐색하겠다는 뜻

 

먼저 그림을 통해

이해를 해보자

 

DFS

 

 

 

이제 위에서 본 그림을 인접리스트를 사용한 JAVA 코드로 풀어보자

 

사용할 LinkedList와 boolean타입의 배열 선언부

/*
 * 먼저 정점들의 연결 다리가 되어줄
 * LinkedList와 
 * 
 * 방문 여부를 확인할
 * boolean 타입의 배열을 선언
 */
public class DFS {
	private LinkedList<Integer> list[]; // 정점들의 인접 리스트를 저장하는 배열
	private boolean visitFlag[]; // 정점 방문 여부를 체크하는 배열
	private BufferedWriter buffWriter; 

	// 그래프 초기화를 위한 생성자
	DFS(int vertices) throws IOException {
		list = new LinkedList[vertices]; 
		visitFlag = new boolean[vertices]; 
		buffWriter = new BufferedWriter(new OutputStreamWriter(System.out)); 

		// 각 정점에 대한 LinkedList 초기화
		for (int i = 0; i < vertices; i++) {
			list[i] = new LinkedList<Integer>();
		}
	}

 

실제 DFS 수행 메소드 선언부

/*
 * 시작점과 도착점을 설정해주고,
 * 
 * 실제 DFS를 수행할 메소드 선언
 * 	- 현재 정점에서 연결된 정점들을 iterator로 모두 방문
 * 	- boolean 배열로 방문 중복 체크 
 * 	- 재귀함수로 구동
 */
void addEdge(int startPoint, int endPoint) {
    list[startPoint].add(endPoint); // startPoint 정점에서 endPoint 정점으로 가는 간선 추가
}


void runDFS(int vertex) throws IOException {
    visitFlag[vertex] = true; // 현재 정점을 방문한 것으로 표시
    buffWriter.write(vertex + " "); // 현재 정점 출력

    // 현재 정점과 연결된 모든 정점들
    Iterator<Integer> iterate = list[vertex].listIterator();
    while (iterate.hasNext()) {
        int adj = iterate.next();

        if (!visitFlag[adj]) // 아직 방문하지 않은 정점에 대해서만
            runDFS(adj); // 재귀적함수
    }
}

 

간선 설정, 탐색 시작과 결과 출력부

/*
 * 간선을 명시하고,
 * 시작 정점을 설정
 * 
 * DFS 실행
 */
public static void main(String args[]) throws IOException {
    DFS init = new DFS(11); // 11개 정점

    // 간선 추가
    init.addEdge(0, 1);
    init.addEdge(1, 3);
    init.addEdge(1, 10);
    init.addEdge(3, 5);
    init.addEdge(3, 7);
    init.addEdge(7, 6);
    init.addEdge(7, 9);
    init.addEdge(0, 2);
    init.addEdge(2, 4);
    init.addEdge(4, 8);

    init.buffWriter.write("DFS 탐색 결과:\n");
    init.runDFS(0); // 정점 0에서 DFS 탐색 시작
    
    init.buffWriter.flush(); 
    init.buffWriter.close(); 
}

/*
 * DFS 탐색 결과:
 * 0 1 3 5 7 6 9 10 2 4 8 
 */

 

 

이러한 구조를 가지며

LinkedList 를 사용할 경우의 시간 복잡도는 O(V + E) 이다

(그래프의 구조와 크기에 따라 달라질 수 있음!!)

 

 V(vertex)는 그래프 정점(노드)의 갯수

E(edge)는 그래프 간선의 갯수이다

 

 

조금 더 파헤쳐보면, DFS의 주요 특성은

" 재귀함수 " 를 사용한다는 것!!

(Stack 으로 대체 가능)

 

추가적으로

DFS를 구현하는 방법에는

1. LIst 로 구현한 DFS

2. Tree 로 구현한 DFS

 두 가지 방안이 존재하는데

 

위에서 봤던 예시는 List 구현 방식의 인접리스트를 사용한 것

 

 

<List 로 구현한 DFS>

List 로 구현하는 방식에는 인접 리스트(LinkedList)와

인접 행렬(2D  Array)방식이 존재하는데

 

 

인접 리스트(LinkedList)의 경우 각 정점에 직접 연결된 정점들만

저장하는 특성 때문에 간선의 수가 정점과 비교해

상대적으로 적은 희소 그래프에 적합하며

 

장점:                                                        

- 필요한 메모리만 사용

- 간선의 추가 삭제 용이

  - 특정 정점과 연결된 정점 탐색이 빠름

 

단점:                                                        

- 전체적인 구조 파악에 다소 어려움 존재

- 두 정점간의 연결 여부 파악하는데 시간 소모

 

 

인접 행렬(2D Array)의 경우 모든 정점 쌍의 연결 정보를

저장하는 특성 때문에 간선의 수가 정점과 비교해

상대적으로 많은 밀집 그래프에 적합하며

 

장점:                                                        

 - 비교적 쉬운 전체 구조 파악

- 두 정점간의 연결 여부 파악이 빠름

 

단점:                                                        

- 간선의 추가 삭제 불편

- 모든 정점의 정보를 저장하기에

(연결되지 않은 정점의 쌍 포함)

비효율적인 메모리 사용

 

 

 

<Tree 로 구현한 DFS>

Tree 로 구현한 DFS 의 경우 계층적인 구조의 특성 때문에

부모와 자식 노드 간 명확한 관계 존재하며

 

장점:                                                        

 - List 보다 더욱 간결한 구조

- 필요한 추가 메모리의 규모가 작음

 

단점:                                                        

- 탐색 순서에 따른

다른 결과값

- 최단 경로 탐색에는 비적합

(최단 경로 보장하지 않음)

 

 

정리해보자면

 

List 로 구현한 DFS는 구조적 복잡성과

사이클 존재 가능성을 고려해야 하며 방문 기록이 필요하고

 

Tree 로 구현한 DFS는 구조가 비교적 단순하며

사이클이 없고, 부모 - 자식 관계에서 탐색이 이루어진다