DFS BFS 정리

DFS BFS 정리

오늘은 dfs, bfs에 대한 설명과 샘플 코드에 대해 포스팅해 보겠습니다.

DFS 란?

depth-first-search로 한국어로 깊이우선탐색이라고 합니다. linked list에서 depth를 내려가면서 탐색을 하는 방법입니다.

샘플 코드

dfs는 stack을 이용해 구현할 수 있습니다. dfs로 linked list를 순회하면서 결과를 list에 담는 함수를 구현한다면, 아래와 같을 것입니다.

def searchTree(root):
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        stack.append(node.right)
        stack.append(node.left)
    return res

BFS 란?

breadth-first-search로 한국어로 너비우선탐색이라고 합니다. linked list에서 같은 depth의 노드들을 모두 확인후 내려가며 탐색을 하는 방법입니다.

샘플 코드

bfs는 queue을 이용해 구현할 수 있습니다. bfs로 linked list를 순회하면서 결과를 list에 담는 함수를 구현한다면, 아래와 같을 것입니다.

def searchTree(root):
    res = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        res.append(node.val)
        stack.append(node.left)
        stack.append(node.right)
    return res

list dfs 샘플 예제

target이 되는 조합을 반환하는 문제

    def combinationSum(self, candidates, target):
        res = []
        self.getCombination(candidates, target, [], res)
        return res
    
    def getCombination(self, cs, target, r, res):
        if target == 0:
            res.append(r)
            return
        if target < 0:
            return
        for c in range(len(cs)):
            self.getCombination(cs[c:], target - cs[c], r + [cs[c]], res)