[Algorithm] 깊이 우선 탐색(Depth First Search)

설명

• 그래프에서 데이터 탐색할 경우 깊이를 우선으로 탐색하는 방식
• 스택을 사용
• 참고
  • https://youtu.be/l0Rsu7dziws

참고 그래프

• DFS
  • 1 2 3 6 7 4 5

DFS 코드

• 그래프 코드는 아래 내용 참고\
  • https://sg-choi.tistory.com/338

재귀를 활용한 방법

public class Solution {
    public static <T> List<T> search(Graph<T> graph, T start) {
        List<T> result = new ArrayList<>();

        dfs(result, graph, start);

        return result;
    }

    private static <T> void dfs(List<T> result, Graph<T> graph, T start) {
        // 현재 노드 방문 표시
        Node<T> node = graph.getNode(start);
        node.setVisited(true);
        result.add(node.getValue());

        for (Node<T> nearNode : node.getNearNodes()) {
            // 인접 노드 중 방문하지 않은 노드를 기준으로 dfs 진행
            if (!nearNode.isVisited()) {
                dfs(result, graph, nearNode.getValue());
            }
        }
    }
}

스택을 활용한 방법

public class Solution {
    public static <T> List<T> search(Graph<T> graph, T start) {
        List<T> result = new ArrayList<>();

        Node<T> node = graph.getNode(start);
        node.setVisited(true);
        result.add(node.getValue());

        Stack<Node<T>> stack = new Stack<>();
        stack.add(node);

        while (true) {
            node = getVisitableNearNode(node);

            if (node != null) {
                node.setVisited(true);
                result.add(node.getValue());
                stack.add(node);
                continue;
            }

            if (stack.isEmpty()) {
                break;
            }

            node = stack.pop();
        }

        return result;
    }

    private static <T> Node<T> getVisitableNearNode(Node<T> node) {
        for (Node<T> nearNode : node.getNearNodes()) {
            if (!nearNode.isVisited()) {
                return nearNode;
            }
        }

        return null;
    }
}

테스트

class SolutionTest extends Specification {
    @Unroll
    def "#graph, #start -> #result"() {
        expect:
        Solution.search(new Graph<Integer>(graph as Integer[][]), start as Integer) == result as List<Integer>

        where:
        graph                                                                    | start | result
        [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 5], [6, 7]] | 1     | [1, 2, 3, 6, 7, 4, 5]
        [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 5], [6, 7]] | 2     | [2, 1, 3, 6, 7, 4, 5]
    }
}