[파이썬] 코딩테스트 13 구현_BFS

BFS (너비 우선 탐색) 완전 정리

---

개념부터 차근차근

BFS는 "너비 우선 탐색(Breadth-First Search)"이라는 뜻으로,
시작점에서 가까운 노드부터 먼저 탐색해 나가는 방식이다.

예를 들어

• 아래와 같은 지도가 있다고 하자.
• 출발점은 1번 노드로 한다.

(📌 참고: 실제 문제에서는 도시나 정점이라고 부를 수도 있음)

• 이 지도를 BFS로 탐색하면 아래와 같은 순서로 방문하게 된다.

→ 즉, 출발점 1번에서 가까운 순으로 2, 3 → 8, 7 → 4, 5, 6 순서로 이동한다.

---

BFS의 핵심 아이디어

• "가까운 곳부터 먼저 방문하자!"
• 이를 위해 **큐(Queue)**를 이용해 방문 순서를 관리한다.
• 큐는 줄 서기처럼 먼저 들어간 게 먼저 나온다 (FIFO 구조)

---

BFS를 구현하는 방식

1. 필요한 준비물

• 방문할 곳 리스트 (need_visit)
  → 앞으로 방문해야 할 노드들을 저장한다.
  → 큐 방식이므로 .pop(0)으로 앞에서부터 꺼낸다.
• 방문한 곳 리스트 (visited)
  → 이미 방문해서 다시 가지 않아도 되는 곳들이다.

---

2. BFS 탐색 흐름 요약

def bfs(graph, start):
    need_visit = []    # 방문할 곳 목록
    visited = []       # 방문한 곳 목록

    need_visit.append(start)  # 출발점 넣고 시작

    while need_visit:         # 방문할 곳이 남아있다면 계속 반복
        node = need_visit.pop(0)  # 큐에서 제일 앞에 있는 노드를 꺼낸다

        if node not in visited:   # 아직 방문하지 않았다면
            visited.append(node)                 # 도장 찍기
            need_visit.extend(graph[node])       # 연결된 노드들을 방문 예정으로 등록

    return visited

 

---

3. 예시 코드 실행 결과

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

bfs(graph, 1)
# 출력: [1, 2, 3, 8, 7, 4, 5, 6]

→ 위의 출력 결과처럼 1에서 시작해서 가까운 순서대로 탐색하는 것을 확인할 수 있다.

---

BFS 작동 원리 자세히 풀어보기

단계	현재 방문할 곳(Queue)	방문 완료 목록(Visited)	꺼낸 노드	연결된 노드
초기	[1]	[]	-	-
1	[]	[1]	1	[2, 3, 8]
2	[3, 8]	[1, 2]	2	[1, 7]
3	[8, 7]	[1, 2, 3]	3	[1, 4, 5]
4	[7, 4, 5]	[1, 2, 3, 8]	8	[1, 7]
5	[4, 5]	[1, 2, 3, 8, 7]	7	[2, 8]
6	[5, 6]	[1, 2, 3, 8, 7, 4]	4	[3, 6]
7	[6]	[1, 2, 3, 8, 7, 4, 5]	5	[3]
8	[]	[1, 2, 3, 8, 7, 4, 5, 6]	6	[4]

---

BFS 정리 요약

항목	설명
탐색 목적	시작점에서 가까운 곳부터 차례로 방문
스케줄링 방식	Queue (큐) 사용 - 먼저 넣은 게 먼저 나옴
반복 구조	while문 (언제 끝날지 모르므로)
핵심 동작	방문할 곳 꺼내기 → 처음 방문이면 도장 찍고, 연결된 곳 추가하기
대표 사용 예시	최단 거리 탐색, 레벨 순서 탐색 등

 

---

Tip: DFS와 BFS 비교

항목	DFS	BFS
방식	깊게 파고들기	넓게 퍼져나가기
구조	Stack(스택) 사용	Queue(큐) 사용
구현	재귀 or 반복	반복 중심 (while문 + 큐)
대표 예시	미로 탈출, 백트래킹	최단 거리 탐색