lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

pythonIntroAlgorithms2Chapter3Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter4Title

def dfs(graph, start, visited=[]):
    if start not in visited:
        visited.append(start)

        for next in graph[start]:
            dfs(graph, next, visited)

    return visited


graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}

print(dfs(graph, 'A'))

# 깊이 우선 탐색(DFS) 구현 방법

## 1. 스택 사용

- DFS는 스택을 사용하여 이미 방문한 노드를 추적합니다. 재귀 호출을 사용하여 스택 구현을 내재화할 수 있습니다.

```python title="스택 사용 예시"
def dfs(graph, start, visited=[]):
    if start not in visited:
        visited.append(start)

        for next in graph[start]:
            if next not in visited:
                dfs(graph, next, visited)

    return visited
```

<br />

## 2. 재귀적 탐색

- 현재 노드에서 방문하지 않은 인접 노드를 찾아 계속해서 탐색을 진행합니다.

```python title="재귀적 탐색 예시"
for next in graph[start]:
    if next not in visited:
        dfs(graph, next, visited)
```

<br />

## 시간 복잡도

1. `시간 복잡도`: (O(V + E))

   - 여기서 `V`는 정점의 수, `E`는 간선의 수를 나타냅니다. 각 정점은 한 번씩 방문되며, 각 간선은 두 번 검사됩니다(양방향).

2. `비순환 그래프에서의 효율성`: DFS는 비순환 그래프에서 모든 노드를 방문하는 데 효과적입니다.

3. `순환 그래프에서의 주의점`: 순환 경로가 있는 그래프에서는 무한 루프에 빠질 위험이 있으므로, 이를 방지하기 위한 추가적인 메커니즘이 필요할 수 있습니다.