DFS 코드 이해하기 ( java )

이번 블로깅은 DFS 코드에 대해 분석하는 내용이라 DFS에 대한 개념을 어느 정도 아는 상태여야 이해가 됩니다.

 

1. 그래프의 탐색

그래프의 탐색은 하나의 정점에서 모든 정점을 차례로 한 번씩 방문하는 것을 의미합니다.

그 알고리즘은 DFS 와 BFS가 있습니다.

 

 

 

2. DFS ( Depth First Search ) - 깊이 우선 탐색

루트 노드나 임의의 노드에서 시작해 깊숙히 탐색한 다음 다시 원점으로 돌아가 다른 루트를 탐색하는 방법입니다.

즉, 다음 노드로 넘어가기 전에 완전 탐색을 하는 방법입니다.

 

일반적으로 재귀, 스택, 인접 행렬, 인접 리스트를 이용해 구현합니다.

 

주로, 미로 탐색과 같이 한 방향으로 계속 탐색해야 하는 경우에 사용되며, 만약 막 다른 곳에 도달하면 그 길에 표식을 남기고

가장 가까운 갈림길로 돌아와 다시 탐색을 진행합니다.

이러한 방법으로 갈림길을 순차적으로 탐색해 목적지까지의 경로를 구합니다.

 

 

 

 * 특징

1) 깊게 탐색

2) 모든 노드를 방문하고자 하는 경우에 사용

3) 노드의 방문 여부를 반드시 검사해야함 ( 그렇지 않으면 무한 루프에 빠질 수 있음 )

4) BFS 에 비해 구현이 쉬움

5) BFS 에 비해 느림

6) 해가 없는 경우에 대한 예외 발생 코드가 필요

7) 해를 구한다고 해도 최단 경로라는 보장은 못함

 

 

 

위의 그래프를 직접 만들고, DFS를 진행해본다고 가정하고 코드를 작성해 보겠습니다.

 

 

[ 소스코드 ]

public class graphDFS {
    private int nV; //정점
    private int[][] dfsGraph; //간선
    private boolean[] visitArr; //방문한 배열

    public graphDFS(int nV) {
        this.nV = nV;

        this.dfsGraph = new int[this.nV + 1][this.nV + 1];
        this.visitArr = new boolean[this.nV + 1];
    }

    // 그래프 리턴
    public int[][] getGraph() {
        return this.dfsGraph;
    }

    // 양방향 그래프 추가
    public void put(int x,int y) {
        this.dfsGraph[x][y] = 1;
        this.dfsGraph[y][x] = 1;
    }

    // 단방향 그래프 추가
    public void putSingle(int x, int y) {
        this.dfsGraph[x][y] = 1;
    }
    //그래프 출력
    public void printGraphToAdjArr() {
        System.out.println("\n"+"[그래프 출력]");
        for (int i = 1; i < dfsGraph.length; i++) {
            for (int j = 1; j < dfsGraph[i].length; j++) {
                System.out.print(this.dfsGraph[i][j]+" ");
            }
            System.out.println();
        }
    }

    // 그래프 탐색
    public void dfs(int vIdx) {
        visitArr[vIdx] = true;
        System.out.print(vIdx + " ");
        for (int i = 1; i <= nV; i++) {
            if(dfsGraph[vIdx][i] == 1 && visitArr[i] == false){
                dfs(i);
            }
        }
    }

    public static void main(String[] args) {
        int nV = 8;

        graphDFS graph = new graphDFS(nV);

        graph.put(1, 2);
        graph.put(1, 3);
        graph.put(2, 4);
        graph.put(2, 5);
        graph.put(3, 6);
        graph.put(3, 7);
        graph.put(4, 8);
        graph.put(5, 8);
        graph.put(6, 8);
        graph.put(7, 8);

        graph.dfs(1);
        graph.printGraphToAdjArr();

    }
}

[ dfs 함수 설명 ]

- visitArr : 탐색을 했다는 걸 알 수 있는 배열

- visitArr[vIdx] = true  : true가 되면 탐색 한 것

- if ( dfsGraph [ vIdx ] [ i ] == 1 : 방문한 인덱스에 다음 정점까지의 경로가 있는 경우

- visitArr[i] : 방문할 정점의 경로가 방문한 적이 없는 경우

- dfs (i) 재귀를 통해 방문한다.