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

DFS(StartNode, GoalTest) {
    Create an empty LIFO Stack
    Create an empty Set Visited
    
    Push(Stack, StartNode)
    
    while (Stack is not empty) {
        currentNode = Pop(Stack)
        
        if (GoalTest(currentNode) == TRUE) {
            return SolutionPath(currentNode)   // 첫 번째 발견된 해 반환
        }
        
        if (currentNode not in Visited) {
            Add(Visited, currentNode)
            
            for each Child in Expand(currentNode) {
                if (Child not in Visited) {
                    Child.parent = currentNode
                    Push(Stack, Child)   // 스택의 맨 위에 추가 (가장 먼저 탐색)
                }
            }
        }
    }
    return FAILURE
}