Depth First Search

DFS(Depth First Search)는 말 그대로 깊이 우선 탐색이다.

바로 예시를 보자.

위와 같은 순서로 노드를 탐색한다.

구현 방식은 다음과 같다.

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

def dfs_recursive(node,visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj,visited)

    return visited

def dfs_stack(start):
    visited = []
    #방문한 순서 담아놓는 용도
    stack = [start]

    #방문할 노드가 남아 있다면 아래 로직 반복
    while stack:
        #제일 최근 노드 꺼내고 방문 처리
        top = stack.pop()
        visited.append(top)

        #인접 노드 방문
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

어떤 문제에서 DFS를 사용하면 좋을지 백준에 나와 있는 문제를 보자.
백준 2606번 링크

정답
1번 컴퓨터가 바이러스에 걸렸을 경우, 이와 인접한 2,5번이 바이러스에 걸린다. 마찬가지로 2,5과 인첩한 3,6번도 바이러스에 걸린다.
문제에서 요구하는 건 1번이 바이러스에 걸렸을 경우 컴퓨터 바이러스에 걸리게 되는 컴퓨터의 수를 구하는 것이므로 2,3,5,6번이 바이러스에 걸려 4개이다.

DFS를 사용해서 1번에서부터 최대로 연결할 수 있는 노드의 개수를 구하면 된다.

---

다른 문제를 살펴보자.

백준 2667번 링크

정답
모든 행렬을 탐색하면서 단지가 존재한다면, 해당 단지에서 부터 DFS를 하여 단지의 최대 개수를 구한 후 저장하는 방식으로 탐색한 후, 오름차순을 해주면 되는 문제이다.

이 문제는 연결할 수 있는 모든 노드를 구하는 것과 다를바 없다.