[Algorithm]그래프 - 3. 깊이 우선 탐색(DFS) - (1) Stack

이전글

[Algorithm]그래프 - 2. 그래프의 구현

 

그래프에서 탐색이란 순서에 따라 모든 데이터를 찾아 내는 것이다. 그래프(graph)는 자료 구조이고 그래프를 탐색하는 방법에는 크게 2가지의 알고리즘이 있다. 하나는 이번 글에서 소개 할 깊이 우선 탐색이고, 하나는 다음 글에서 소개 할 너비 우선 탐색이다. 들어가기 앞서 둘의 차이점을 먼저 파악해 보자.

• 깊이 우선 탐색(DFS)은 가장 깊은 노드까지 먼저 탐색하고 더이상 탐색 할 노드가 없으면 이전 노드로 되돌아간 다음 탐색하지 않았던 노드의 가장 깊은 노드까지 탐색하는 방법이다.

< DFS의 탐색순서 = A, B, C, D, E, F >

• 너비 우선 탐색(BFS)은 이웃 노드를 모두 탐색하고 다음 깊이에 있는 노드를 탐색하는 방법이다.

< BFS의 탐색순서 = A, E, C, D, F >

깊이 우선 탐색이란?

• 그래프의 탐색방법 중 한 종류 이다.
• 깊이 우선 탐색(depth-first search)은 시작 노드부터 탐색을 시작해서 간선을 따라 최대의 깊이 노드까지 이동하며 차례대로 방문한다.
• 최대 깊이 노드까지 도착한 다음에는 다시 이전 노드로 돌아가 노드 중 방문하지 않은 노드가 있다면 방문하지 않은 노드 방향으로 최대 깊이까지 차례대로 방문한다.
• 더이상 방문하지 않은 노드가 없으면 탐색을 종료 한다.
• 구현 방법은 스택을 활용한 방법과 재귀 함수를 활용한 방법 두가지가 있다.

스택을 활용한 깊이 우선 탐색

• 깊이 우선 탐색에 사용 될 스택 자료구조를 생성 한다.
• 방문한 노드를 재방문을 하면 안되기 때문에 방문 여부를 확인 할 배열이 필요하다. (배열의 길이는 노드 수만큼 필요)
• 시작 노드를 스택에 Push해 준다.
• 스택의 값이 없을 때 까지 반복되는 while 문을 작성 한다.
• while문 안에서 스택에서 노드를 꺼낸 후 방문 처리를 한다.
• 노드의 근접 노드를 확인하고 방문하지 않은 노드가 있으면 해당 노드를 Stack에 Push 한다.
• 이때 Stack의 먼저 들어간 노드가 나중에 나오는 FILO 특성 때문에 작은 노드 부터 방문하고 싶다면 큰노드 부터 Push, 큰 노드부터 방문하고 싶으면 작은 노드 부터 Push 해야한다. 
• 모든 노드가 방문 되면 탐색이 끝난다.(Stack에 값이 없으면 while문 종료)

public class DFSExgample {

   public static void main(String[] args) {
        new DFSExgample().doRecurseDFS();
    }
    
    void doStackDFS() {
    	// 셈플 데이터
        int[][] elements = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}};
        new DFS_Stack().solution(elements);
    }

    public void solution(int[][] elements) {
        // 깊이 우선 탐색에 사용 될 스택 자료구조를 생성 한다.
        Stack<Integer> stack = new Stack<>();
        //  방문 여부를 확인 할 배열
        boolean[] visist = new boolean[elements.length];
        // visist의 모든 값을 false로 초기화
        Arrays.fill(visist, false);

        // 시작 노드를 스택에 Push해 준다.
        stack.push(0);

        while(!stack.isEmpty()) { // 스택의 값이 없을 때 까지 반복
            // 스택에서 노드를 꺼낸다.
            int node = stack.pop();
            visist[node] = true; // 방문 처리

            // int[] -> Integer[]로 형변환.
            Integer[] nextNodes = Arrays.stream(elements[node]).boxed().toArray(Integer[]::new);
            // 내림차순 정렬
            Arrays.sort(nextNodes, Collections.reverseOrder());
            
            for(int i = elements[node].length-1; i >= 0; i--) { // 노드의 근접 노드를 확인
                int nextNode = elements[node][i];
                if(!visist[nextNode]) { // 방문하지 않은 노드가 있으면
                    stack.push(nextNode); // 해당 노드를 Stack에 Push 한다.
                }
            }

        }

    }
    
}

• 노드의 근접 노드를 확인하는 for문을 보면 뒤 index부터 돌도록 되어있는데 작은 노드 부터 방문하기 위함 이다. 큰 노드 부터 방문 하고 싶다면 for문을 아래 처럼 바꿔 주면 된다.

for(int nextNode : elements[node]) { // 노드의 근접 노드를 확인
    if(!visist[nextNode]) { // 방문하지 않은 노드가 있으면
        stack.push(nextNode); // 해당 노드를 Stack에 Push 한다.
    }
}

• 지금은 샘플 데이터가 잘 정렬이 되어 있기 때문에 따로 정렬을 해 주지 않아도 노드 방문 순서를 지정할 수 있지만 실제 데이터에서 데이터가 정렬되어 있다라는 보장이 없다. 따라서 방문 순서를 지정하고 싶다면 노드를 원하는 방향의 반대 방향으로 정렬해 주어야 한다.

// int[] -> Integer[]로 형변환. 
Integer[] nextNodes = Arrays.stream(elements[node]).boxed().toArray(Integer[]::new);
Arrays.sort(nextNodes, Collections.reverseOrder()); // 내림차순 정렬

for(int nextNode : nextNodes) { // 노드의 근접 노드를 확인
    if(!visist[nextNode]) { // 방문하지 않은 노드가 있으면
        stack.push(nextNode); // 해당 노드를 Stack에 Push 한다.
    }
}

• 내림 차순 정렬을 적용한 소스를 시각화 하면 다음과 같다.

< 탐색 시작 >

< 0 노드 방문 >

< 1 노드 방문 >

< 3 노드 방문 >

< 4 노드 방문 >

< 2 노드 방문 >

< 5 노드 방문 >

• 방문 순서는 0, 2, 3, 4, 2, 5 이다.

다음글

[Algorithm]그래프 - 3. 깊이 우선 탐색(DFS) - 재귀