8.1 BFS ์๊ณ ๋ฆฌ์ฆ์ ์๋ ์๋ฆฌ
๋๋น ์ฐ์ ํ์ (Breadth-First Search, BFS)๋ ๊ทธ๋ํ๋ฅผ ์ํํ๊ฑฐ๋ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ์์ ์ ์ ์์ ์์ํ์ฌ ํ์ฌ ๋ ๋ฒจ์ ์๋ ๋ชจ๋ ์ธ์ ์ ์ ์ ํ์ํ ํ ๋ค์ ๋ ๋ฒจ์ ์ ์ ์ผ๋ก ์ด๋ํฉ๋๋ค.
์๊ณ ๋ฆฌ์ฆ ๋จ๊ณ:
- ์ ํ๋ ์์ ์ ์ ์์ ์์ํ์ฌ ํ์ ๋ฃ์ต๋๋ค.
- ํ๊ฐ ๋น ๋๊น์ง ๋ค์์ ์ํํฉ๋๋ค:
- ํ์ ๋งจ ์์์ ์ ์ ์ ๊บผ๋ด์ด ๋ฐฉ๋ฌธํ๋ค๊ณ ํ์ํฉ๋๋ค.
- ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ์ ์ ์ ๋ชจ๋ ํ์ ์ถ๊ฐํฉ๋๋ค.
- ์์ ์ ์ ์์ ๋๋ฌ ๊ฐ๋ฅํ ๋ชจ๋ ์ ์ ์ ๋ฐฉ๋ฌธํ ๋๊น์ง 2๋จ๊ณ๋ฅผ ๋ฐ๋ณตํฉ๋๋ค.
์๊ฐํ:

์๊ฐ ๋ณต์ก๋:
O(V + E)
์ฌ๊ธฐ์ V
๋ ์ ์ ์ ์, E
๋ ๊ฐ์ ์ ์์
๋๋ค.
๊ทธ๋ํ์ ๋ชจ๋ ๋ ธ๋์ ๊ฐ์ ์ ํ ๋ฒ์ฉ ๋ฐฉ๋ฌธ๋ฉ๋๋ค.
๊ณต๊ฐ ๋ณต์ก๋:
O(V)
, ํ์ ์ ์ ์ ์ ์ฅํ๊ธฐ ์ํด ์ฌ์ฉ๋๋ฉฐ, ์ํ(๋ฐฉ๋ฌธํ ์ ์ )๋ฅผ ์ ์ฅํ๊ธฐ ์ํ ๋ฐฐ์ด๋ ์ฌ์ฉ๋ฉ๋๋ค.
8.2 ํ๋ฅผ ํ์ฉํ BFS ๊ตฌํ
๋๋น ์ฐ์ ํ์์ ํ์ ๊ฐ์ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํ๋ฉด ํจ๊ณผ์ ์ผ๋ก ๊ตฌํ๋ฉ๋๋ค.
ํ๋ฅผ ์ฌ์ฉํ BFS ๊ตฌํ:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex) # ๋
ธ๋ ์ฒ๋ฆฌ
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
# ์ฌ์ฉ ์์:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B'],
'F': ['C']
}
bfs(graph, 'A')
8.3 ์๋ฐฉํฅ ๋๋น ์ฐ์ ํ์
BFS๋ ์ข ์ข ๊ฒ์์์ ๋ ์ง์ ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ์ ๋ ์ฌ์ฉ๋ฉ๋๋ค. ์ด๋ฌํ ๋ฌธ์ ๋ ๋ ์ ์ ์ฌ์ด์ ๊ทธ๋ํ ๊ฒฝ๋ก ํ์ ๋ฌธ์ ๋ก ์ฝ๊ฒ ๋ณํ๋ฉ๋๋ค. ๊ทธ๋ํ์ ๊ฐ์ ์ ์ง๋์์์ ๋ชจ๋ ํต๊ณผ ๊ฐ๋ฅํ ๊ฒฝ๋ก์ ๋๋ค.
ํ์ง๋ง ๋ ๋น ๋ฅด๊ฒ ๊ฒฝ๋ก๋ฅผ ์ฐพ๊ธฐ ์ํด ๋ ๋์์ ๊ฒฝ๋ก๋ฅผ ์ฐพ์์ผ ํฉ๋๋ค. ์ด๋ฅผ ์ํด ์๋ฐฉํฅ BFS๊ฐ ์ฌ์ฉ๋ฉ๋๋ค.
์๋ ์๋ฆฌ
์๋ฐฉํฅ ๋๋น ์ฐ์ ํ์ (Bidirectional BFS)์ BFS๋ฅผ ์ต์ ํํ ๋ฒ์ ์ผ๋ก, ์์ ์ ์ ๊ณผ ๋ชฉํ ์ ์ ์์ ๊ฐ๊ฐ ๋ ๊ฐ์ ๋ณ๋ ฌ ๊ทธ๋ํ ์ํ๋ฅผ ์ํํฉ๋๋ค. ๋ ์ํ๊ฐ ๊ต์ฐจ๋ ๋๊น์ง ์งํ๋๋ฉฐ, ์ด๋ ์ ํต์ ์ธ BFS์ ๋นํด ํจ์ฌ ์ ์ ์ ์ ๊ณผ ๊ฐ์ ์ ๊ฒ์ฌํ๋๋ก ํฉ๋๋ค.
์๊ณ ๋ฆฌ์ฆ ๋จ๊ณ:
- ์์ ์ ์ ์์์ ์ํ๋ฅผ ์ํ ํ์ ๋ชฉํ ์ ์ ์์์ ํ ๋ ๊ฐ๋ฅผ ์ด๊ธฐํํฉ๋๋ค.
- ๋ ๋ฐฉํฅ์์์ ๋ฐฉ๋ฌธํ ์ ์ ์ ์ถ์ ํ๊ธฐ ์ํด ๋ ๊ฐ์ ๋ฐฉ๋ฌธ ์ ์ ์งํฉ์ ์ด๊ธฐํํฉ๋๋ค.
- ๋ ํ๋ก๋ถํฐ ๋ฒ๊ฐ์ ๊ฐ๋ฉฐ ๊ทธ๋ํ๋ฅผ ์ํํฉ๋๋ค.
- ๊ฐ ๋จ๊ณ์์ ๋ฐฉ๋ฌธํ ์ ์ ์งํฉ์ด ๊ต์ฐจํ๋์ง ํ์ธํฉ๋๋ค. ๊ต์ฐจ๊ฐ ๋ฐ๊ฒฌ๋๋ฉด ๊ฒฝ๋ก๊ฐ ์กด์ฌํฉ๋๋ค.
- ๊ต์ฐจ ๋ ธ๋๊ฐ ๋ฐ๊ฒฌ๋๊ฑฐ๋ ํ๊ฐ ๋น ๋๊น์ง ๊ณผ์ ์ ๊ณ์ํฉ๋๋ค.
์๊ฐ ๋ณต์ก๋
์ต์์ ๊ฒฝ์ฐ: O(2 * (V + E)) = O(V + E)
, ์ฌ๊ธฐ์ V
๋ ์ ์ ์ ์, E
๋ ๊ฐ์ ์ ์์
๋๋ค.
์๋ฐฉํฅ BFS๋ ํฐ ๊ทธ๋ํ์์ ๋จ๋ฐฉํฅ BFS๋ณด๋ค ์ผ๋ฐ์ ์ผ๋ก ๋ ์ ์ ์ ์ ์ ์ํํฉ๋๋ค.
๊ณต๊ฐ ๋ณต์ก๋:
O(V)
๋ ํ์ ๋ ๊ฐ์ ๋ฐฉ๋ฌธ ์ ์ ์งํฉ์ ์ ์ฅํ๊ธฐ ์ํด ์ฌ์ฉ๋ฉ๋๋ค.
์๋ฐฉํฅ BFS์ ์์ ๊ตฌํ
์์๋ ๋งค์ฐ ๊ธธ๊ธฐ ๋๋ฌธ์ ๋จ๋ฐฉํฅ ํ์๋ณด๋ค ์ธ ๋ฐฐ ์ ๋ ๊ธธ์ด์ ์ฌ๊ธฐ์๋ ์๋ตํฉ๋๋ค. ๋์ค์ ํ์ํ ๋๋ ์ค์ค๋ก ์์ฑํ ์ ์์ ๊ฒ๋๋ค.
8.4 BFS๋ฅผ ์ฌ์ฉํ์ฌ ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์์
BFS๋ฅผ ์ฌ์ฉํ์ฌ ํด๊ฒฐํ ์ ์๋ ์ ํ์ ์ธ ๋ฌธ์ ์์:
1. ๋ฌดํฅ ๊ทธ๋ํ์์ ์ต๋จ ๊ฒฝ๋ก ์ฐพ๊ธฐ:
BFS๋ ์์ ์ ์ ์์ ๋ชฉํ ์ ์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก(์ต์ ๊ฐ์ ์)๋ฅผ ์ฐพ๋ ๋ฐ ์ฌ์ฉ๋ฉ๋๋ค.
์ ์ฉ ๋ถ์ผ:
- ๋ค๋น๊ฒ์ด์ ์์คํ ์์ ์ง์ ๊ฐ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๊ธฐ ์ํด.
- ๋คํธ์ํฌ ๋ถ์์์ ๋ฐ์ดํฐ ์ ์ก์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๊ธฐ ์ํด.
2. ๊ทธ๋ํ ์ฐ๊ฒฐ์ฑ ๊ฒ์ฌ:
๊ทธ๋ํ๊ฐ ์ฐ๊ฒฐ๋์ด ์๋์ง, ์ฆ ์ด๋ค ๋ ์ ์ ์ฌ์ด์ ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๋์ง ํ์ธ.
์ ์ฉ ๋ถ์ผ:
- ๋คํธ์ํฌ ๋ถ์์์ ๋คํธ์ํฌ์ ์ฐ๊ฒฐ์ฑ์ ํ์ธํ๊ธฐ ์ํด.
- ์์ ๋คํธ์ํฌ ๋ถ์์์ ์ฌ์ฉ์ ๊ทธ๋ฃน์ ์ฐ๊ฒฐ์ฑ์ ํ์ธํ๊ธฐ ์ํด.
3. ๋ฏธ๋ก ์์ฑ:
BFS๋ฅผ ์ฌ์ฉํ์ฌ ์ฃผ์ด์ง ์์ฑ์ ๊ฐ์ง ๋๋ค ๋ฏธ๋ก ์์ฑ.
์ ์ฉ ๋ถ์ผ:
- ๊ฒ์ ์ ํ๋ฆฌ์ผ์ด์ ์์ ๋ฏธ๋ก๋ฅผ ์์ฑํ๊ธฐ ์ํด.
- ๋ก๋ด ๊ณตํ์์ ๋ด๋น๊ฒ์ด์ ์๊ณ ๋ฆฌ์ฆ ํ ์คํธ๋ฅผ ์ํด.
4. ํธ๋ฆฌ์์ ๋๋น ์ฐ์ ํ์:
BFS๋ ํธ๋ฆฌ๋ฅผ ์ํํ์ฌ ํธ๋ฆฌ์ ๊ฐ ๋ ๋ฒจ์์ ์์ ์ ์ํํ๋ ๋ฐ ์ฌ์ฉ๋ฉ๋๋ค (์: ๊ฐ ๋ ๋ฒจ์ ๋ชจ๋ ๋ ธ๋ ์ถ๋ ฅ).
์ ์ฉ ๋ถ์ผ:
- ๋ฐ์ดํฐ ์๊ฐํ ๋ฌธ์ ์์ ๋ ๋ฒจ๋ณ๋ก ๋ฐ์ดํฐ๋ฅผ ํ์ํด์ผ ํ ๋.
- ๊ณํ ๋ฌธ์ ์์ ๊ณ์ธต ๊ตฌ์กฐ์ ๊ฐ ๋ ๋ฒจ์์ ์์ ์ ์ํํด์ผ ํ ๋.
5. ์ด๋ถ ๊ทธ๋ํ ๊ฒ์ฌ:
๊ทธ๋ํ๊ฐ ์ด๋ถ ๊ทธ๋ํ์ธ์ง, ์ฆ ๋ ๊ฐ์ ์งํฉ์ผ๋ก ๋๋ ์ ์๊ณ , ๊ฐ์ ์ด ์๋ก ๋ค๋ฅธ ์งํฉ์ ์ ์ ์ฌ์ด์๋ง ์กด์ฌํ๋์ง๋ฅผ ํ์ธ.
์ ์ฉ ๋ถ์ผ:
- ๊ทธ๋ํ ์ด๋ก ์์ ๊ทธ๋ํ์ ์ด๋ถ์ฑ์ ํ์ธํ๊ธฐ ์ํด.
- ๊ทธ๋ํ ์ปฌ๋ฌ๋ง ๋ฌธ์ ์์ ๊ทธ๋ํ๋ฅผ ๋ ๊ฐ์ง ์์ผ๋ก ์น ํ ์ ์๋์ง ํ์ธํ๊ธฐ ์ํด.