DFS - Depth First Search

오늘은 너비우선 탐색을 알아보겠습니다. 

DFS는 BFS와 같이 배우는 경우가 많은데요.

BFS는 지난 포스팅에서 다루었기 때문에 필요하다면 참고해보셔도 좋을 것 같아요 〰️ 

 

 

DFS❓

DFS는 Depth First Search의 약자입니다.

너비 우선 탐색으로, 연결되어 있는 모든 노드를 전부 확인하고 그 다음 노드의 모든 노드를 살펴보는 방식으로 모든 노드를 탐색하는 방식이죠.

 

DFS와 BFS의 비교는 지난 포스팅에서 이미 다뤘기 때문에 생략하겠습니다.

 

 

DFS 구현

 

노드들이 연결되어 있다고 가정하겠습니다.

아래의 그림에서 왼쪽은 보기 편하게 도식화한 모습이고, 오른 쪽의 위는 linked List로 구현되어 있는 모습을 표시했습니다,

Visited는 Boolean 타입의 Array입니다.

 

 

위의 그림에서 가장 먼저 시작하는 노드를 먼저 시작하면 그 노드를 기준으로 연결되어 있는 노드를 모두 방문합니다.

방문을 했다면, visited 배열 중 해당하는 인덱스를 True로 표시합니다.

 

응용을 한다면, 단순 visited의 값을 바꾸는 게 아닌 추가적인 로직이 추가될 수도 있겠죠?추가적인 부분을 잘생각해서 표현하는 기술이 굉장히 중요하다고 생각해요.

 

자, 이렇게 첫 번째 노드를 방문했다면, 연결되어 있는 노드를 모두 확인합니다. BFS와 같은 경우는 Queue를 두어 방문할 노드를 저장해두지만, DFS는 Queue를 사용하지 않고 순회합니다.

 

어떻게 가능할까요❓ 코드에서도 확인할 수 있겠지만, '재귀'를 사용합니다. 이 정도만 알아두고 더 자세하게 알아볼게요 〰️ 그래야 더 흥미로울 것 같네요 😝

 

 

더 먼저 연결되어 있는 노드를 방문하고 visited에 데이터를 표시해줍니다.

더 연결된 노드가 있다면 그 노드들을 순차적으로 방문하죠.

 

그래서 2와 연결되어 있던 0과 3을 방문한 것입니다. 

만약, BFS였다면, 0을 방문하고 1을 방문했겠죠.

 

그 다음엔 똑같습니다.

방문한 노드에 연결된 노드들을 전부 순회하죠.

 

이때, 확인해야할 조건은 visited가 False일 때만입니다.

이 조건을 갖고 있는 이유는, Visited라는 Array가 없다면 방문한 곳을 계속 돌기 때문에 굉장히 오랜 시간이 걸리거나 무한 루프에 빠질 가능성이 크기 때문입니다.

 

3도 마찬가지 입니다.

자기 자신을 갖고 있는데요. 

접근하려고 도전은 하지만, visited가 False이기 때문에 다른 로직은 실행하지 못합니다.

 

응용을 한다면, 조건에 맞춰 visited를 다른 타입으로 설정할 수도 있습니다.

 

 

자, 이제 개념은 이해했으니 코드를 살펴보도록 하겠습니다.

 

 

BFS 구현 - JAVA CODE

 

import java.io.*;
import java.util.*;

class DFS {
    private int V; // No. of vertices
    private LinkedList<Integer> adj[];

    DFS(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w); // Add w to v's list.
    }

    void dfs(int v,boolean visited[]) {
        visited[v] = true;
        System.out.print(v+" ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                dfs(n, visited);
        }
    }

    public static void main(String args[]) {
        DFSwithGraph g = new DFSwithGraph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        
        boolean visited[] = new boolean[V];
        dfs(2, visited);
    }
}

 

코드의 addEdge는 인접리스트를 만들어주는 역할뿐이니 무시하셔도 됩니다. 중요한 건 dfs 메소드입니다. visited에 방문하는 v번에 해당하는 Boolean 데이터를 변경합니다.

 

방문한 다음 방문한 순서를 확인하기 위해 출력을 했습니다.그 다음 연결된 모든 노드를 while을 사용해서 순회하죠. 만약, 방문한 적이 없는 노드면 dfs 호출로 방문합니다.

 

 

 

 

 

그럼 여기까지 DFS에 대해 알아보았습니다.

개념은 이해했는데 응용하는게 상당히 어렵더라구요 ㅜㅠ

좀 더 노력해야겠다는 마음이 크게 드는 포스팅이었습니다