Java DFS(Depth First Search) 구현하기

Java DFS(Depth First Search) 구현하기

Java로 DFS(Depth First Search)를 구현하는 방법에 대해 알아보겠습니다.

1. 그래프의 탐색

그래프의 탐색은 하나의 정점으로부터 시작하여 모든 정점을 차례대로 한 번씩 방문하는 것을 의미합니다. 예를 들어 특정 도시에서 다른 도시로의 이동 여부 판별이나 회로에서 단자와 단자의 연결 여부 확인 등에 사용됩니다. 

그래프 탐색에서 대중적으로 많이 알려진 알고리즘은 DFS와 BFS가 있는데 이번 포스팅에서는 DFS에 대해서 알아보도록 하겠습니다.

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

깊이 우선 탐색(DFS)는 루트 노드나 임의의 노드에서 시작하여 최대한 깊숙히 들어가서 탐색한 후 다시 원점으로 돌아가 다른 루트로 탐색하는 방식입니다. 즉, 다음 노드로 넘어가기 전에 해당 노드의 분기에 대해 완전 탐색을 하는 방식입니다. 

일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택이나 인접 행렬, 인접 리스트를 이용하여 구현하기도 합니다. (스택을 사용할 경우엔 오버플로우를 유의해야 합니다)

DFS는 자동 미로 생성 또는 미로 탐색에 사용되는데 다음과 같은 특징이 있습니다.

• 미로 탐색시 한 방향으로 갈 수 있을 때까지 계속 탐색.
  막다른 곳에 도달하면 막다른 길에 대한 표식을 남기고 가장 가까운 갈림길로 돌아와 다시 탐색을 진행.
  이러한 방법으로 갈림길을 순차적으로 탐색하여 목적지까지의 경로를 구함.
• 넓게(Breadth) 탐색하기 전에 깊게(Depth) 탐색함
• 모든 노드를 방문하고자 하는 경우에 사용
  
• 자기 자신을 호출하는 순환 알고리즘의 형태 (재귀호출)
• 노드 방문 여부를 반드시 검사해야 함.
  이렇게 하지 않을 경우 무한 루프에 빠질 위험이 있음

DFS의 장점과 단점은 다음과 같습니다.

장점	단점
구현이 너비 우선 탐색(BFS) 보다 간단하다 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음	단순 검색 속도는 너비 우선 탐색(BFS) 보다 느림 해가 없는 경우에 빠질 가능성이 있음 (이러한 경우 사전에 임의의 깊이를 지정한 후 탐색하도록 하고, 목표 노드를 발견하지 못할 경우 다음 경로를 탐색하도록 함) 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없음 (목표에 이르는 경로가 다수인 경우 구한 해가 최적이 아닐 수 있음)

3. DFS 구현 

다음의 그래프를 대상으로 인접 행렬과 인접 리스트를 사용하여 DFS를 구현해보겠습니다.

구현에 앞서, 위의 그래프를 1번 정점부터 순차적으로 탐색했을 때 어떻게 동작하는지 알아보겠습니다.

• 1번 정점 : 2번, 3번 정점을 모두 방문하지 않은 상태
  2번 정점 방문
• 2번 정점 : 1번, 4번, 5번 정점과 연결된 상태이고 1번 정점은 방문한 상태
  4번 정점 방문
• 4번 정점 : 2번, 8번 정점과 연결된 상태이고 2번 정점은 방문한 상태
  8번 정점 방문
• 8번 정점 : 4번, 5번, 6번, 7번 정점과 연결된 상태이고 4번 정점은 방문한 상태
  5번 정점 방문
  
• 5번 정점 : 2번, 8번 정점과 연결된 상태이고 연결된 정점은 모두 방문한 상태
  이전에 방문한 정점으로 돌아감 (8번 정점)
  
• 8번 정점 : 4번, 5번, 6번, 7번 정점과 연결된 상태이고 4번, 5번 정점은 방문한 상태
  6번 정점 방문
• 6번 정점 : 3번, 8번 정점과 연결된 상태이고 8번 정점은 방문한 상태
  3번 정점 방문
• 3번 정점 : 1번, 6번, 7번 정점과 연결된 상태이고 1번, 6번 정점은 방문한 상태
  7번 정점 방문
• 7번 정점 : 3번, 8번 정점과 연결된 상태이고 연결된 정점은 모두 방문한 상태
  이전에 방문한 정점으로 돌아감 (8번 정점)
• 8번 정점 : 4번, 5번, 6번, 7번 정점과 연결된 상태이고 연결된 정점은 모두 방문한 상태
  더 이상 방문할 정점이 없으므로 탐색 종료

재귀호출에 대한 이해를 바탕으로 순차적으로 흐름을 따라가보면 위와 같이 탐색이 진행되는 것을 확인할 수 있습니다.

3.1 인접 행렬을 이용한 DFS 구현 

다음은 양방향 인접 행렬을 사용하여 2차원 배열로 구현한 DFS 소스코드입니다.

import java.util.Scanner;
 
/*
 * @ TITLE DFS(Depth First Search)
 * @ COMMENT
 *     인접행렬을 이용한 DFS 구현
 */
// 그래프(인접행렬) 클래스
class DfsGraph {
    private int nV;    // 정점의 개수
    private int[][] dfsGraph;    // 그래프
    private boolean[] visitArr;    // 정점 방문 여부 확인 배열
 
    // 그래프 초기화
    public DfsGraph(int nV) {
        this.nV = nV;
        
        // 그래프 초기화
        // put(int x, int y) 에서 입력되는 정점의 값은 0 이상의 정수이나
        // 배열의 index는 0 부터 시작이므로 
        // ArrayIndexOutOfBoundsException 방지를 위해 
        // 정점을 담는 인접행렬의 행과 열 size는 1을 더하여 초기화해줌
        this.dfsGraph = new int[this.nV+1][this.nV+1];
        
        // 정점 방문 여부 확인 배열 초기화
        // 그래프와 마찬가지로 정점의 개수에 +1하여 초기화
        this.visitArr = new boolean[this.nV+1];
    }
 
    // 그래프 return
    public int[][] getGraph() {
        return this.dfsGraph;
    }
 
    // 그래프 추가 (양방향)
    public void put(int x, int y) {
        // 정점 x와 y가 연결되어있음을 의미
        this.dfsGraph[x][y] = this.dfsGraph[y][x] = 1;
    }
 
    // 그래프 추가 (단방향)
    public void putSingle(int x, int y) {
        this.dfsGraph[x][y] = 1;
    }
    
    // 그래프 출력 (인접행렬)
    public void printGraphToAdjArr() {
        for(int i=0; i<this.dfsGraph.length; i++) {
            for(int j=0; j<this.dfsGraph[i].length; j++) {
                System.out.print(" " + this.dfsGraph[i][j]);
            }
            System.out.println();
        }
    }
    
    // 정점 방문 여부 확인 배열 초기화
    public void clearVisitArr() {
        for(int i=0; i<this.visitArr.length; i++) {
            this.visitArr[i] = false;
        }
    }
    
    // 그래프 탐색 (재귀호출)
    public void dfs(int vIdx) {
        // dfs()에 들어온 vIdx는 방문한 것이므로
        // 방문배열의 해당 index값을 true로 바꿔주고 값을 출력함.
        this.visitArr[vIdx] = true;
        System.out.print(vIdx + " "); 
        
        // 인접 행렬로 구현된 그래프에서
        // 정점의 개수(nV) 만큼 탐색
        for(int i=1; i<=this.nV; i++) {
            
            // dfsGraph[][]의 해당 정점이 연결되어있는 것으로 표시되어 있으나 (연결은 1로 표시)
            // 방문 배열에서 방문하지 않은 상태(false)인 경우
            if(dfsGraph[vIdx][i] == 1 && visitArr[i] == false) {
                dfs(i);    // dfs() 재귀호출
            }
        }
    }
 
}
    
public class DFSAdjArr {
    public static void main(String[] args) {
        // int v = 0;    // 정점 (수동입력에 사용되는 변수)
        // int e = 0;    // 간선 (수동입력에 사용되는 변수)
        int nV = 0;    // 정점의 개수
        int nE = 0;    // 간선의 개수
        
        Scanner sc = new Scanner(System.in);
        nV = sc.nextInt();    // 정점
        nE = sc.nextInt();    // 간선
        
        // 입력받은 정점의 개수로 그래프 초기화
        DfsGraph dfsGraph = new DfsGraph(nV);
        
        // 그래프에 정점과 간선 입력
        // 입력받은 간선의 개수만큼 반복
        // ex) 정점 8, 간선 10
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        // 정점과 간선 수동 입력
        /*for(int i=0; i<nE; i++) {
            v = sc.nextInt();
            e = sc.nextInt();
            dfsGraph.put(v, e);
        }*/
        
        sc.close();
        
        // 입력한 정점과 간선으로 구성된 인접행렬 출력
        dfsGraph.printGraphToAdjArr();
        
        // 정점 순서대로 그래프 탐색
        System.out.println();
        System.out.print("정점 1부터 탐색 : ");
        dfsGraph.dfs(1);
        
        System.out.println();
        System.out.print("정점 2부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(2);
        
        System.out.println();
        System.out.print("정점 3부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(3);
        
        System.out.println();
        System.out.print("정점 4부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(4);
        
        System.out.println();
        System.out.print("정점 5부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(5);
        
        System.out.println();
        System.out.print("정점 6부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(6);
        
        System.out.println();
        System.out.print("정점 7부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(7);
        
        System.out.println();
        System.out.print("정점 8부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(8);
    }
}

실행 결과는 다음과 같습니다.

3.2 인접 리스트를 이용한 DFS 구현 

다음은 인접 리스트를 이용하여 구현한 DFS 소스코드입니다.

import java.util.ArrayList;
import java.util.Scanner;
 
/*
 * @ TITLE DFS(Depth First Search)
 * @ COMMENT
 *     인접리스트를 이용한 DFS 구현
 */
// 그래프(인접리스트) 클래스
class DfsGraph {
    private int nV;    // 정점의 개수
    private ArrayList<ArrayList<Integer>> dfsGraph;    // 그래프
    private boolean[] visitArr;    // 정점 방문 여부 확인 배열
 
    // 그래프 초기화 생성자
    public DfsGraph(int nV) {
        this.nV = nV;    // 정점 개수 초기화
        this.dfsGraph = new ArrayList<ArrayList<Integer>>(); // 그래프 생성
        
        // 그래프 초기화
        // put(int x, int y) 에서 입력되는 정점의 값은 0 이상의 정수이나
        // ArrayList의 index는 0 부터 시작이므로 
        // ArrayIndexOutOfBoundsException 방지를 위해 
        // 정점을 담는 인접리스트의 size는 1을 더하여 초기화해줌
        // 즉, 입력받은 정점의 개수에 +1을 해줌
 
        // ex) initSize = 3
        // graph[0]
        // graph[1] -> 2 -> 3
        // graph[2] -> 1 -> 3 -> 4
        // graph[3] -> 1 -> 2 -> 4 -> 5
        for(int i=0; i<this.nV+1; i++) {
            this.dfsGraph.add(new ArrayList<Integer>());
        }
        
        // 정점 방문 여부 확인 배열 초기화
        // 그래프와 마찬가지로 정점의 개수에 +1하여 초기화
        this.visitArr = new boolean[this.nV+1];
    }
 
    // 그래프 return
    public ArrayList<ArrayList<Integer>> getGraph() {
        return this.dfsGraph;
    }
 
    // 그래프의 특정 노드 return
    public ArrayList<Integer> getNode(int i) {
        return this.dfsGraph.get(i);
    }
 
    // 그래프 추가 (양방향)
    public void put(int x, int y) {
        this.dfsGraph.get(x).add(y);
        this.dfsGraph.get(y).add(x);
    }
 
    // 그래프 추가 (단방향)
    public void putSingle(int x, int y) {
        this.dfsGraph.get(x).add(y);
    }
    
    // 그래프 출력 (인접리스트)
    public void printGraphToAdjList() {
        for(int i=1; i<this.dfsGraph.size(); i++) {
            System.out.print("정점 " + i + "의 인접리스트");
            
            for(int j=0; j<this.dfsGraph.get(i).size(); j++) {
                System.out.print(" -> " + this.dfsGraph.get(i).get(j));
            }
            System.out.println();
        }
    }
    
    // 정점 방문 여부 확인 배열 초기화
    public void clearVisitArr() {
        for(int i=0; i<this.visitArr.length; i++) {
            this.visitArr[i] = false;
        }
    }
    
    // 그래프 탐색 (재귀호출)
    public void dfs(int vIdx) {
        // dfs()에 파라미터로 넘어온 vIdx는 방문한 것이므로
        // 방문배열의 해당 index값을 true로 바꿔주고 값을 출력함.
        this.visitArr[vIdx] = true;
        System.out.print(vIdx + " "); 
        
        // 인접리스트로 구현된 그래프에서
        // 해당 index에 맞는 리스트를 가져와서 반복
        for(int i : this.dfsGraph.get(vIdx)) {
            
            // 해당 정점(i)이 정점 방문 여부 확인 배열에서
            // 방문하지 않은 상태(false)인 경우
            if(this.visitArr[i] == false) {
                dfs(i);    // dfs() 재귀호출
            }
        }
    }
 
}
    
public class DFSAdjList {
    public static void main(String[] args) {
        // int v = 0;    // 정점 (수동입력에 사용되는 변수)
        // int e = 0;    // 간선 (수동입력에 사용되는 변수)
        int nV = 0;    // 정점의 개수
        int nE = 0;    // 간선의 개수
        
        Scanner sc = new Scanner(System.in);
        nV = sc.nextInt();    // 정점
        nE = sc.nextInt();    // 간선
        
        // 입력받은 정점의 개수로 그래프 초기화
        DfsGraph dfsGraph = new DfsGraph(nV);
        
        // 그래프에 정점과 간선 입력
        // 입력받은 간선의 개수만큼 반복
        // ex) 정점 8, 간선 10
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        // 정점과 간선 수동 입력
        /*for(int i=0; i<nE; i++) {
            v = sc.nextInt();
            e = sc.nextInt();
            dfsGraph.put(v, e);
        }*/
        
        sc.close();
        
        // 입력한 정점과 간선으로 구성된 인접리스트 출력
        dfsGraph.printGraphToAdjList();
        
        // 정점 순서대로 그래프 탐색
        System.out.println();
        System.out.print("정점 1부터 탐색 : ");
        dfsGraph.dfs(1);
        
        System.out.println();
        System.out.print("정점 2부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(2);
        
        System.out.println();
        System.out.print("정점 3부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(3);
        
        System.out.println();
        System.out.print("정점 4부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(4);
        
        System.out.println();
        System.out.print("정점 5부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(5);
        
        System.out.println();
        System.out.print("정점 6부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(6);
        
        System.out.println();
        System.out.print("정점 7부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(7);
        
        System.out.println();
        System.out.print("정점 8부터 탐색 : ");
        dfsGraph.clearVisitArr();
        dfsGraph.dfs(8);
    }
}

실행 결과는 다음과 같습니다.

인접 행렬과 인접 리스트를 이용하여 구현한 DFS의 경우 사용된 자료구조(배열 or 리스트)의 형태는 다르지만 결과는 동일하게 출력되는 것을 확인할 수 있습니다.

정점과 간선으로 이루어진 그래프에서 맞는 경우에 따라 DFS를 사용하기 위해서는, 인접 행렬과 인접 리스트가 각각 가지고 있는 특징과 차이점에 대한 이해가 필요합니다.

이상으로 Java 인접 행렬과 인접 리스트를 이용한 DFS 구현 방법에 대해 알아봤습니다.

※ 참고 문헌

• manducku.tistory.com, 알고리즘 Graph - DFS(깊이 우선 탐색), https://manducku.tistory.com/23

• ktko.tistory.com, (탐색알고리즘) 깊이 우선 탐색(DFS : Depth First Search), https://ktko.tistory.com/entry/%ED%83%90%EC%83%89%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-Depth-First-Search

• gmlwjd9405.github.io, [알고리즘] 깊이 우선 탐색(DFS)이란, https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html