lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

pythonIntroAlgorithms2Chapter3Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter4Title

def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            # 리스트를 이용하여 중복 제거
            queue.extend([n for n in graph[node] if n not in visited])

    return visited

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

print(bfs(graph, 'A'))

# 너비 우선 탐색(BFS) 구현 방법

## 1. 큐 사용

- BFS는 큐를 사용하여 탐색할 노드들을 관리합니다. 큐를 사용하여 각 레벨별로 노드를 순차적으로 탐색합니다.

```python title="큐 사용 예시"
def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            # 리스트를 이용하여 중복 제거
            queue.extend([n for n in graph[node] if n not in visited])

    return visited
```

<br />

## 2. 레벨별 탐색

- BFS는 각 노드의 레벨별로 인접 노드를 탐색합니다. 이는 큐의 선입선출(FIFO) 특성을 활용합니다.

```python title="레벨별 탐색 예시"
while queue:
    node = queue.pop(0)
    if node not in visited:
        visited.append(node)
        # 리스트를 이용하여 중복 제거
        queue.extend([n for n in graph[node] if n not in visited])
```

<br />

## 시간 복잡도

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

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

2. `최단 경로 탐색`: BFS는 무방향 그래프에서 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 효과적입니다.

3. `넓은 범위 탐색`: BFS는 레벨별 탐색을 통해 넓은 범위의 노드들을 효과적으로 탐색할 수 있습니다.