DFS, BFS 알고리즘

오랫만에 개인적으로 알고리즘에 관해서 질문을 받았다.

요즘은 Next.js, ts, js 에 대해 깊게 공부하고 있는 중이라 알고리즘 공부를 소흘히 했었는데, 뭔가 다시 반성하게 되는 느낌이 되어서 DFS, BFS 알고리즘에 대해서 간단히 다시 생각해보려고 한다.

DFS 알고리즘은 깊이 우선 탐색으로, 주로 최단 경로 문제나 백트래킹 문제에 사용된다.
BFS 알고리즘은 주로 그래프 순회에 주로 사용된다.

주어진 인접 리스트가 아래와 같다고 할 때

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}

• DFS

def dfs(start_v):
    visited = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)
    return visited
    
def recursive_dfs(v, visited=[]):
	visited.append(v)
    for w in graph[v]:
    	if w not in visited:
        	visited = recursive_dfs(w, visited)
    return visited
      

• BFS

def bfs(start_v):
    visited = []
    deq = deque([start_v])
    while deq:
        v = deq.popleft()
        print(deq)
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                deq.append(w)

    return visited

순회할 때, 인접 리스트들을 모두 하나씩 확인하는지 아니면 하나의 인접리스트를 계속 순회 할 것인지에 대한 방향 차이가 있지만, 알고리즘 문제가 뭘 원하는지에 따라서 다르게 사용하면 된다.