설명 : BFS(너비 우선 탐색) 알고리즘은 그래프나 트리에서 한 노드로부터 시작하여 인접한 모든 노드를 먼저 방문하는 알고리즘입니다. 이 알고리즘은 큐(queue)를 사용하여 구현됩니다. 큐에는 방문할 노드들이 차례대로 저장되어 있으며, 먼저 들어온 노드를 먼저 방문합니다.
BFS의 구체적인 동작 과정
1. 시작 노드를 큐에 넣고 방문 여부를 표시합니다.
2. 큐가 빌 때까지 다음 과정을 반복합니다.
- 큐에서 하나의 노드를 꺼냅니다.
- 해당 노드의 인접한 노드들 중 방문하지 않은 노드들을 큐에 넣고 방문 여부를 표시합니다.
3. 큐가 비면 탐색을 종료합니다.
BFS 알고리즘을 파이썬으로 구현한 예시
--------------------------------------------------------------------------------------------------
from collections import defaultdict, deque
def bfs(graph, start):
visited = set() # 방문한 노드를 저장할 집합
queue = deque([start]) # 큐에 시작 노드를 넣습니다.
while queue:
# 큐에서 노드를 하나 꺼냅니다.
node = queue.popleft()
# 만약 그 노드가 방문하지 않은것이면
if node not in visited:
# 방문한 노드를 집합에 추가합니다.
visited.add(node)
# 현재 노드의 인접한 노드들에 대해
for neighbor in graph[node]:
# 방문하지 않은 경우에만 큐에 넣습니다.
if neighbor not in visited:
queue.append(neighbor)
#이후 while문 내에서 queue가 popleft에 의해 빌때까지, 반복됨
# 그래프를 인접 리스트로 표현. 리스트를 값으로 가지는 딕셔너리를 생성
# defaultdict(list) 의 동작은 존재하지 않는 키에 접근하면 기본값을 생성하고,
# 기존에 존재하는 키에 대해서는 기본값이 생성되지 않는다.
graph = defaultdict(list)
graph[1] = [2, 3]
graph[2] = [1, 4, 5]
graph[3] = [1, 6]
graph[4] = [2]
graph[5] = [2, 7]
graph[6] = [3]
graph[7] = [5]
# 시작 노드를 1로 설정하고 BFS를 실행합니다.
start_node = 1
print("BFS 탐색 결과:")
bfs(graph, start_node)
--------------------------------------------------------------------------------------------------
이 코드는 다음과 같은 그래프를 탐색하는 BFS 알고리즘입니다.
1
/ \
2 3
| \ \
4 5 6
|
7
자세한 동작
1. 시작 노드 1을 먼저 방문합니다. 그 다음으로, 1과 인접한 노드들인 2와 3이 큐에 순서대로 추가됩니다.
2. 큐에서 노드를 하나씩 꺼내면서 인접한 노드들을 방문합니다. 먼저 2를 꺼내서 방문하고, 2와 인접한 노드들인 1(이미 방문했으므로 제외), 4, 5가 큐에 추가됩니다.
3. 이어서 3을 꺼내서 방문하고, 3과 인접한 노드들인 1(이미 방문했으므로 제외), 6이 큐에 추가됩니다.
4. 그 다음으로 큐에서 4를 꺼내서 방문하고, 4와 인접한 노드는 없으므로 큐에 추가할 노드가 없습니다.
5. 5를 꺼내서 방문하고, 5와 인접한 노드는 2, 7입니다. 그러나 2는 이미 방문한 노드이므로 큐에 추가하지 않고, 7만 큐에 추가됩니다.
6. 마지막으로 6을 꺼내서 방문하고, 6과 인접한 노드인 3(이미 방문했으므로 제외)만 큐에 추가됩니다.
7. 큐에는 더 이상 내용이(방문할 노드) 없으므로 BFS 탐색을 종료합니다.
출력결과
BFS 탐색 결과:
1 2 3 4 5 6 7
이 코드에서는 defaultdict와 deque를 사용하여 간단한 그래프를 표현하고 BFS 알고리즘을 구현하였습니다.
BFS 알고리즘을 적용할 여러 예시
1. **최단 경로 찾기**: 그래프나 트리에서 두 노드 사이의 최단 경로를 찾는 문제에 BFS를 사용할 수 있습니다. 출발 노드로부터 레벨별로 탐색하면서 도착 노드를 찾으면, 그 경로가 최단 경로입니다.
2. **네트워크 탐색**: 컴퓨터 네트워크나 소셜 네트워크에서 특정 사용자와 연결된 모든 사용자를 찾는 문제에 BFS를 사용할 수 있습니다. 특정 사용자로부터 시작하여 친구, 친구의 친구, 그리고 그 이상으로 네트워크를 탐색할 수 있습니다.
3. **미로 찾기**: 미로를 해결하는 문제에 BFS를 사용할 수 있습니다. 시작 지점에서부터 모든 가능한 경로를 탐색하여 도착 지점까지의 최단 경로를 찾을 수 있습니다.
4. **트리의 너비 계산**: 트리에서 각 레벨의 노드 수를 계산하는 문제에 BFS를 사용할 수 있습니다. 루트 노드부터 시작하여 각 레벨의 노드를 탐색하면서 레벨마다 카운트를 증가시킬 수 있습니다.
5. **게임 탐색**: 보드 게임이나 퍼즐 게임에서 가능한 모든 상태를 탐색하는 문제에 BFS를 사용할 수 있습니다. 현재 상태에서 가능한 모든 다음 상태를 찾아내고, 그 상태에서 가능한 모든 다음 상태를 탐색하며 게임을 진행합니다.
6. **컴퓨터 네트워크 라우팅**: 네트워크에서 최적의 경로를 찾는 문제에 BFS를 사용할 수 있습니다. 시작 노드에서부터 모든 경로를 탐색하고, 목적지에 도달할 때까지 가장 짧은 경로를 선택합니다.
7. **최단 경로 게임**: 게임에서 출발점에서 도착점까지 최단 경로로 이동하는 문제에 BFS를 사용할 수 있습니다. 가능한 모든 이동 경로를 탐색하여 최단 경로를 찾을 수 있습니다.
이러한 예시들은 BFS 알고리즘이 다양한 문제에 적용될 수 있음을 보여줍니다. BFS는 탐색하는 과정에서 레벨별로 탐색하기 때문에 최단 경로를 찾거나 네트워크를 탐색하는 등 다양한 문제에 유용하게 사용될 수 있습니다.
'코딩테스트' 카테고리의 다른 글
| 프로그래머스 오답노트 모음 (0) | 2023.12.15 |
|---|